An undirected graph has n vertices, numbered 0 to n - 1, and m weighted edges. Print the length of the shortest path from vertex 0 to every vertex, or -1 if a vertex cannot be reached. No two edges join the same pair of vertices.
What to build
Dijkstra's algorithm, finding the shortest distance from vertex 0 to every vertex.
Requirements
- Start with distance 0 for vertex 0 and infinity for the others.
- Each round, finish the closest unfinished vertex and relax its edges.
- Print -1 for a vertex that cannot be reached.
Input
The first line has n and m (1 ≤ n ≤ 100, 0 ≤ m ≤ 1000). Each of the next m lines has an edge u v weight (1 ≤ weight ≤ 1000).
Output
The n distances, in vertex order, separated by spaces.
Constraints
1 ≤ n ≤ 100, 0 ≤ m ≤ 1000 and 1 ≤ weight ≤ 1000.
Example
Input:
5 7
0 1 4
0 2 1
1 2 2
1 3 5
2 3 8
3 4 2
2 4 10
Output:
0 3 1 8 10
Why it works
With no negative edges, no later route can get back to the closest unfinished vertex more cheaply, so its distance is final.
Examples
5 7 0 1 4 0 2 1 1 2 2 1 3 5 2 3 8 3 4 2 2 4 10
0 3 1 8 10
3 1 0 1 7
0 7 -1
Hints
Hint 1
Store weights in a matrix w[100][100], with 0 for no edge (weights are at least 1).
Hint 2
Each round, pick the unfinished vertex with the smallest dist, mark it finished, and relax its edges.
Hint 3
Print -1 for a vertex whose dist is still INF at the end.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
#define INF 1000000000
int w[100][100];
int main(void) {
int n, m;
scanf("%d %d", &n, &m);
for (int i = 0; i < m; i++) {
int u, v, c;
scanf("%d %d %d", &u, &v, &c);
w[u][v] = w[v][u] = c;
}
int dist[100], done[100];
for (int i = 0; i < n; i++) {
dist[i] = INF;
done[i] = 0;
}
dist[0] = 0;
for (int round = 0; round < n; round++) {
int u = -1;
for (int i = 0; i < n; i++)
if (!done[i] && (u == -1 || dist[i] < dist[u])) u = i;
if (dist[u] == INF) break; // the rest cannot be reached
done[u] = 1;
for (int v = 0; v < n; v++)
if (w[u][v] && dist[u] + w[u][v] < dist[v]) dist[v] = dist[u] + w[u][v];
}
for (int i = 0; i < n; i++) {
if (i > 0) printf(" ");
printf("%d", dist[i] == INF ? -1 : dist[i]);
}
printf("\n");
return 0;
}