100162024-03-24 09:57:01111Autópálya inflációpypy3Elfogadva 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)
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva48ms76764 KiB
2Elfogadva787ms98700 KiB
subtask28/8
3Elfogadva456ms96492 KiB
4Elfogadva504ms97920 KiB
5Elfogadva732ms98176 KiB
6Elfogadva561ms97108 KiB
7Elfogadva702ms97896 KiB
subtask315/15
8Elfogadva48ms78112 KiB
9Elfogadva43ms78148 KiB
10Elfogadva48ms78248 KiB
11Elfogadva43ms78400 KiB
12Elfogadva50ms78404 KiB
13Elfogadva48ms78080 KiB
14Elfogadva50ms78088 KiB
15Elfogadva43ms78548 KiB
16Elfogadva48ms78484 KiB
17Elfogadva45ms78516 KiB
18Elfogadva41ms79252 KiB
subtask434/34
19Elfogadva469ms98524 KiB
20Elfogadva656ms100256 KiB
21Elfogadva644ms99136 KiB
22Elfogadva375ms98520 KiB
23Elfogadva465ms98300 KiB
24Elfogadva745ms99696 KiB
25Elfogadva476ms98216 KiB
26Elfogadva500ms99984 KiB
27Elfogadva632ms103040 KiB
28Elfogadva607ms100872 KiB
29Elfogadva615ms100388 KiB
30Elfogadva546ms100376 KiB
31Elfogadva620ms101372 KiB
32Elfogadva601ms99880 KiB
33Elfogadva620ms100812 KiB
subtask521/21
34Elfogadva128ms92756 KiB
35Elfogadva141ms94996 KiB
36Elfogadva144ms94444 KiB
37Elfogadva144ms95088 KiB
38Elfogadva129ms94584 KiB
39Elfogadva141ms95100 KiB
40Elfogadva178ms97108 KiB
41Elfogadva194ms97456 KiB
42Elfogadva111ms93320 KiB
43Elfogadva116ms92848 KiB
44Elfogadva115ms92508 KiB
45Elfogadva109ms92700 KiB
46Elfogadva119ms93104 KiB
47Elfogadva115ms92984 KiB
48Elfogadva133ms93560 KiB
49Elfogadva126ms93044 KiB
subtask622/22
50Elfogadva823ms100204 KiB
51Elfogadva783ms102228 KiB
52Elfogadva517ms101448 KiB
53Elfogadva504ms101004 KiB
54Elfogadva570ms101756 KiB
55Elfogadva630ms100976 KiB
56Elfogadva686ms104960 KiB
57Elfogadva651ms104728 KiB
58Elfogadva171ms93948 KiB
59Elfogadva624ms100748 KiB
60Elfogadva657ms100652 KiB
61Elfogadva598ms100604 KiB
62Elfogadva660ms100288 KiB
63Elfogadva663ms100840 KiB
64Elfogadva554ms100868 KiB
65Elfogadva629ms102076 KiB
66Elfogadva587ms99764 KiB