100152024-03-24 09:55:11111Autópálya inflációpypy3Runtime error 0/100165ms102308 KiB
import math

N, M = map(int, input().split())
g = [[] for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append((b, c))
    g[b].append((a, c))

dp = [[math.inf, math.inf] for _ in range(N)]
dp[0][0] = 0

for i in range(N - 1):
    v = []
    for j in range(N):
        if i > 0 and dp[j][i % 2] >= dp[j][(i % 2) ^ 1]:
            dp[j][i % 2] = dp[j][(i % 2) ^ 1]
            continue
        v.append(j)
    for j in v:
        for k, w in g[j]:
            dp[k][(i % 2) ^ 1] = min(dp[k][(i % 2) ^ 1], dp[j][i % 2] + w * ipow(2, i))

for i in range(1, N):
    print(int(min(dp[i]) % 1000000007))
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Runtime error90ms89308 KiB
2Runtime error140ms95668 KiB
subtask20/8
3Runtime error141ms96244 KiB
4Runtime error134ms96212 KiB
5Runtime error141ms96536 KiB
6Runtime error141ms96936 KiB
7Runtime error133ms97288 KiB
subtask30/15
8Runtime error87ms91372 KiB
9Runtime error82ms91480 KiB
10Runtime error89ms91724 KiB
11Runtime error82ms91808 KiB
12Runtime error92ms92032 KiB
13Runtime error82ms92436 KiB
14Runtime error89ms92312 KiB
15Runtime error89ms92224 KiB
16Runtime error89ms92736 KiB
17Runtime error90ms92932 KiB
18Runtime error90ms92944 KiB
subtask40/34
19Runtime error165ms99056 KiB
20Runtime error138ms99100 KiB
21Runtime error164ms99652 KiB
22Runtime error148ms99168 KiB
23Runtime error140ms99016 KiB
24Runtime error146ms99164 KiB
25Runtime error140ms99588 KiB
26Runtime error146ms99708 KiB
27Runtime error164ms101316 KiB
28Runtime error143ms98796 KiB
29Runtime error136ms99376 KiB
30Runtime error130ms99308 KiB
31Runtime error130ms99352 KiB
32Runtime error136ms100208 KiB
33Runtime error164ms100392 KiB
subtask50/21
34Runtime error114ms94904 KiB
35Runtime error125ms97624 KiB
36Runtime error130ms97424 KiB
37Runtime error130ms97592 KiB
38Runtime error125ms97288 KiB
39Runtime error130ms97524 KiB
40Runtime error123ms97252 KiB
41Runtime error119ms97204 KiB
42Runtime error101ms93836 KiB
43Runtime error94ms93600 KiB
44Runtime error100ms93552 KiB
45Runtime error93ms93644 KiB
46Runtime error90ms93536 KiB
47Runtime error90ms93620 KiB
48Runtime error112ms94604 KiB
49Runtime error105ms94412 KiB
subtask60/22
50Runtime error136ms100024 KiB
51Runtime error146ms100164 KiB
52Runtime error164ms99692 KiB
53Runtime error148ms100560 KiB
54Runtime error149ms100176 KiB
55Runtime error140ms99948 KiB
56Runtime error160ms102308 KiB
57Runtime error160ms102072 KiB
58Runtime error103ms94392 KiB
59Runtime error130ms99872 KiB
60Runtime error143ms99640 KiB
61Runtime error136ms99556 KiB
62Runtime error143ms100112 KiB
63Runtime error136ms100084 KiB
64Runtime error149ms99660 KiB
65Runtime error149ms100360 KiB
66Runtime error142ms99888 KiB