100162024-03-24 09:57:01111Autópálya inflációpypy3Accepted 100/100823ms104960 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 * pow(2, i))

for i in range(1, N):
    print(min(dp[i]) % 1000000007)
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted48ms76764 KiB
2Accepted787ms98700 KiB
subtask28/8
3Accepted456ms96492 KiB
4Accepted504ms97920 KiB
5Accepted732ms98176 KiB
6Accepted561ms97108 KiB
7Accepted702ms97896 KiB
subtask315/15
8Accepted48ms78112 KiB
9Accepted43ms78148 KiB
10Accepted48ms78248 KiB
11Accepted43ms78400 KiB
12Accepted50ms78404 KiB
13Accepted48ms78080 KiB
14Accepted50ms78088 KiB
15Accepted43ms78548 KiB
16Accepted48ms78484 KiB
17Accepted45ms78516 KiB
18Accepted41ms79252 KiB
subtask434/34
19Accepted469ms98524 KiB
20Accepted656ms100256 KiB
21Accepted644ms99136 KiB
22Accepted375ms98520 KiB
23Accepted465ms98300 KiB
24Accepted745ms99696 KiB
25Accepted476ms98216 KiB
26Accepted500ms99984 KiB
27Accepted632ms103040 KiB
28Accepted607ms100872 KiB
29Accepted615ms100388 KiB
30Accepted546ms100376 KiB
31Accepted620ms101372 KiB
32Accepted601ms99880 KiB
33Accepted620ms100812 KiB
subtask521/21
34Accepted128ms92756 KiB
35Accepted141ms94996 KiB
36Accepted144ms94444 KiB
37Accepted144ms95088 KiB
38Accepted129ms94584 KiB
39Accepted141ms95100 KiB
40Accepted178ms97108 KiB
41Accepted194ms97456 KiB
42Accepted111ms93320 KiB
43Accepted116ms92848 KiB
44Accepted115ms92508 KiB
45Accepted109ms92700 KiB
46Accepted119ms93104 KiB
47Accepted115ms92984 KiB
48Accepted133ms93560 KiB
49Accepted126ms93044 KiB
subtask622/22
50Accepted823ms100204 KiB
51Accepted783ms102228 KiB
52Accepted517ms101448 KiB
53Accepted504ms101004 KiB
54Accepted570ms101756 KiB
55Accepted630ms100976 KiB
56Accepted686ms104960 KiB
57Accepted651ms104728 KiB
58Accepted171ms93948 KiB
59Accepted624ms100748 KiB
60Accepted657ms100652 KiB
61Accepted598ms100604 KiB
62Accepted660ms100288 KiB
63Accepted663ms100840 KiB
64Accepted554ms100868 KiB
65Accepted629ms102076 KiB
66Accepted587ms99764 KiB