Routers are numbered 1 to n and joined by two-way links with costs. Using distance-vector routing (the Bellman-Ford rule: a router's cost to a destination is the smallest "link cost to a neighbour + that neighbour's cost"), find router 1's final cost to every router.
Input
A line with n and m (1 ≤ n ≤ 50, 0 ≤ m ≤ 200). Then m lines u v c: a link between routers u and v with cost c (1 ≤ c ≤ 100). There may be more than one link between two routers.
Output
n lines: router 1's cost to router 1, 2, …, n, or unreachable.
Examples
4 4 1 2 1 2 3 2 1 3 5 3 4 1
0 1 3 4
3 1 1 2 7
0 7 unreachable
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Keep dist[d] = router 1's best known cost to d: 0 for itself, infinity for the rest.
Hint 2
Repeat until nothing changes: for every link (u, v, c), if dist[u] + c < dist[v], improve dist[v] (and the same the other way, links work both ways).
Hint 3
This is Bellman-Ford: at most n - 1 rounds are needed.
Solution
Show one correct solution (try it yourself first)
n, m = map(int, input().split())
links = [tuple(map(int, input().split())) for _ in range(m)]
INF = float("inf")
dist = [INF] * (n + 1)
dist[1] = 0
changed = True
while changed:
changed = False
for u, v, c in links:
if dist[u] + c < dist[v]:
dist[v] = dist[u] + c
changed = True
if dist[v] + c < dist[u]:
dist[u] = dist[v] + c
changed = True
for d in range(1, n + 1):
print(dist[d] if dist[d] < INF else "unreachable")
Lesson: Routing algorithms: link state and distance vector →