10016 2024. 03. 24 09:57:01 111 Autópálya infláció pypy3 Elfogadva 100/100 823ms 104960 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 Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 48ms 76764 KiB
2 Elfogadva 787ms 98700 KiB
subtask2 8/8
3 Elfogadva 456ms 96492 KiB
4 Elfogadva 504ms 97920 KiB
5 Elfogadva 732ms 98176 KiB
6 Elfogadva 561ms 97108 KiB
7 Elfogadva 702ms 97896 KiB
subtask3 15/15
8 Elfogadva 48ms 78112 KiB
9 Elfogadva 43ms 78148 KiB
10 Elfogadva 48ms 78248 KiB
11 Elfogadva 43ms 78400 KiB
12 Elfogadva 50ms 78404 KiB
13 Elfogadva 48ms 78080 KiB
14 Elfogadva 50ms 78088 KiB
15 Elfogadva 43ms 78548 KiB
16 Elfogadva 48ms 78484 KiB
17 Elfogadva 45ms 78516 KiB
18 Elfogadva 41ms 79252 KiB
subtask4 34/34
19 Elfogadva 469ms 98524 KiB
20 Elfogadva 656ms 100256 KiB
21 Elfogadva 644ms 99136 KiB
22 Elfogadva 375ms 98520 KiB
23 Elfogadva 465ms 98300 KiB
24 Elfogadva 745ms 99696 KiB
25 Elfogadva 476ms 98216 KiB
26 Elfogadva 500ms 99984 KiB
27 Elfogadva 632ms 103040 KiB
28 Elfogadva 607ms 100872 KiB
29 Elfogadva 615ms 100388 KiB
30 Elfogadva 546ms 100376 KiB
31 Elfogadva 620ms 101372 KiB
32 Elfogadva 601ms 99880 KiB
33 Elfogadva 620ms 100812 KiB
subtask5 21/21
34 Elfogadva 128ms 92756 KiB
35 Elfogadva 141ms 94996 KiB
36 Elfogadva 144ms 94444 KiB
37 Elfogadva 144ms 95088 KiB
38 Elfogadva 129ms 94584 KiB
39 Elfogadva 141ms 95100 KiB
40 Elfogadva 178ms 97108 KiB
41 Elfogadva 194ms 97456 KiB
42 Elfogadva 111ms 93320 KiB
43 Elfogadva 116ms 92848 KiB
44 Elfogadva 115ms 92508 KiB
45 Elfogadva 109ms 92700 KiB
46 Elfogadva 119ms 93104 KiB
47 Elfogadva 115ms 92984 KiB
48 Elfogadva 133ms 93560 KiB
49 Elfogadva 126ms 93044 KiB
subtask6 22/22
50 Elfogadva 823ms 100204 KiB
51 Elfogadva 783ms 102228 KiB
52 Elfogadva 517ms 101448 KiB
53 Elfogadva 504ms 101004 KiB
54 Elfogadva 570ms 101756 KiB
55 Elfogadva 630ms 100976 KiB
56 Elfogadva 686ms 104960 KiB
57 Elfogadva 651ms 104728 KiB
58 Elfogadva 171ms 93948 KiB
59 Elfogadva 624ms 100748 KiB
60 Elfogadva 657ms 100652 KiB
61 Elfogadva 598ms 100604 KiB
62 Elfogadva 660ms 100288 KiB
63 Elfogadva 663ms 100840 KiB
64 Elfogadva 554ms 100868 KiB
65 Elfogadva 629ms 102076 KiB
66 Elfogadva 587ms 99764 KiB