fork download
copy 
  1. import sys
  2.  
  3. def solve():
  4.     data = sys.stdin.read().split()
  5.     if not data:
  6.         return
  7.  
  8.     it = iter(data)
  9.     n = int(next(it))
  10.     m = int(next(it))
  11.  
  12.     adj = [[] for _ in range(n + 1)]
  13.     for _ in range(m):
  14.         u = int(next(it))
  15.         v = int(next(it))
  16.         w = int(next(it))
  17.         adj[u].append((v, w))
  18.         adj[v].append((u, w))
  19.  
  20.     dist = [float('inf')] * (n + 1)
  21.     vis = [False] * (n + 1)
  22.     dist[1] = 0
  23.  
  24.     for _ in range(n):
  25.         u = -1
  26.         for i in range(1, n + 1):
  27.             if not vis[i] and (u == -1 or dist[i] < dist[u]):
  28.                 u = i
  29.  
  30.         if u == -1 or dist[u] == float('inf'):
  31.             break
  32.  
  33.         vis[u] = True
  34.         for v, w in adj[u]:
  35.             if dist[u] + w < dist[v]:
  36.                 dist[v] = dist[u] + w
  37.  
  38.     for i in range(2, n + 1):
  39.         print(dist[i] if dist[i] != float('inf') else -1)
  40.  
  41. if __name__ == "__main__":
  42.     solve()
Success #stdin #stdout 0.1s 13996KB
comments (?)
stdin
copy 
5 6
1 5 2
2 1 6
3 4 2
4 2 9
5 3 7
2 3 4
stdout
copy 
6
9
11
2
https://ideone.com/oNokVi
language:
Python 3 (python  3.12)
created:
5 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!