-
Notifications
You must be signed in to change notification settings - Fork 6
/
catchingnoodles.py
32 lines (28 loc) · 955 Bytes
/
catchingnoodles.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import sys
from heapq import *
from array import *
MOD, L = 10**9 + 7, 10**7 + 3
v, e = map(int, input().split())
g = [array('q') for _ in range(v)]
for l in sys.stdin:
a, b, w = map(int, l.split())
g[a].append(b*L+w), g[b].append(a*L+w)
def dijkstra(s):
D = array('q', [10**18]*v)
D[s], p, pq = 0, [0]*v, [s]
p[s] = 1
while pq:
u = heappop(pq)
dd, vv = u//L, u%L
if dd == D[vv]:
for nnww in g[vv]:
nn, ww = nnww//L, nnww%L
if D[nn] > dd + ww:
D[nn], p[nn] = dd + ww, p[vv]
heappush(pq, D[nn]*L+nn)
elif D[nn] == dd + ww:
p[nn] = (p[nn] + p[vv]) % MOD
return D, p
(D1, p1), (D2, p2) = dijkstra(v-1), dijkstra(0)
if D1[0] == 1e18: print(*[-1]*v)
else: print(*[(p1[i]*p2[i]) % MOD if D1[i] + D2[i] == D1[0] else -1 for i in range(v)])