Mr.Awesome's blog

Jzzhu and Cities WA (dijkstra)
By Mr.Awesome, history, 9 years ago, In English

I'm getting WA in this 449B this is my submission

i implemented the dijkstra's algorithm to find shortest path between the capital and each city , and the result is stored in dist[] .

could anyone point out the problem , or tell me if my idea is wrong ??

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Did you considered that maybe the shortest path between capital and a city will use one train route and some other roads?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No because the statement inform that train's routes can only connect a city and the capital directly and not 2 cities .

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      The shortest path between 1 and X could be a train route between 1 and Y and then a path(the shortest path) between Y and X...

      → Reply