Editorial for COCI '07 Contest 6 #4 George
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
We model the city as an undirected weighted graph. When Mister George traverses an edge, we can consider the weight of that edge to change over time. For example, if Mister George enters a street during minute and the street has weight
, then the weight changes like this:
| Time | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|---|---|---|---|---|---|---|---|
| Weight | 5 | 10 | 9 | 8 | 7 | 6 | 5 |
After thinking about it, we conclude that the problem can be solved with Dijkstra's shortest path algorithm, with the weight of an edge depending on when we use it.
Comments