UVa 10986

From Algorithmist
Jump to navigation Jump to search

10986 - Sending email[edit]

Summary[edit]

Find length of the shortest path between two vertices in an undirected graph with non-negative edges' weights.

Explanation[edit]

Dijkstra's algorithm will do. You may need to use STL's priority_queue ot implement your own binary heap to make Dijkstra run in time.

Solutions[edit]

Input[edit]

3
2 1 0 1
0 1 100
3 3 2 0
0 1 100
0 2 200
1 2 50
2 0 0 1

Output[edit]

Case #1: 100
Case #2: 150
Case #3: unreachable