fork download
copy 
  1. import sys
  2. import heapq
  3. from collections import deque
  4.  
  5. input = sys.stdin.readline
  6. INF = float('inf')
  7.  
  8. while True:
  9.     n, m = map(int, input().split())
  10.     if n == 0 and m == 0:
  11.         break
  12.  
  13.     s, d = map(int, input().split())
  14.     graph = [[] for _ in range(n)]
  15.     rgraph = [[] for _ in range(n)]
  16.  
  17.     for _ in range(m):
  18.         u, v, p = map(int, input().split())
  19.         graph[u].append((v, p))
  20.         rgraph[v].append((u, p))
  21.  
  22.     dist = [INF] * n
  23.     dist[s] = 0
  24.     heap = [(0, s)]
  25.     while heap:
  26.         cost, u = heapq.heappop(heap)
  27.         if cost > dist[u]:
  28.             continue
  29.         for v, w in graph[u]:
  30.             if cost + w < dist[v]:
  31.                 dist[v] = cost + w
  32.                 heapq.heappush(heap, (dist[v], v))
  33.  
  34.     if dist[d] == INF:
  35.         print(-1)
  36.         continue
  37.  
  38.     q = deque([d])
  39.     while q:
  40.         cur = q.popleft()
  41.         for prev, w in rgraph[cur]:
  42.             if dist[prev] + w == dist[cur]:
  43.                 for i, (nv, w2) in enumerate(graph[prev]):
  44.                     if nv == cur and w2 == w:
  45.                         graph[prev][i] = (-1, -1)
  46.                 q.append(prev)
  47.  
  48.     dist2 = [INF] * n
  49.     dist2[s] = 0
  50.     heap = [(0, s)]
  51.     while heap:
  52.         cost, u = heapq.heappop(heap)
  53.         if cost > dist2[u]:
  54.             continue
  55.         for v, w in graph[u]:
  56.             if v == -1:
  57.                 continue
  58.             if cost + w < dist2[v]:
  59.                 dist2[v] = cost + w
  60.                 heapq.heappush(heap, (dist2[v], v))
  61.  
  62.     print(-1 if dist2[d] == INF else dist2[d])
  63.  
Success #stdin #stdout 0.13s 14176KB
comments (?)
stdin
copy 
7 9
0 6
0 1 1
0 2 1
0 3 2
0 4 3
1 5 2
2 6 4
3 6 2
4 6 4
5 6 1
4 6
0 2
0 1 1
1 2 1
1 3 1
3 2 1
2 0 3
3 0 2
6 8
0 1
0 1 1
0 2 2
0 3 3
2 5 3
3 4 2
4 1 1
5 1 1
3 0 1
0 0
stdout
copy 
5
-1
6
https://ideone.com/SPDQbG
language:
Python 3 (python  3.12)
created:
2 days 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!