10015 2024. 03. 24 09:55:11 111 Autópálya infláció pypy3 Futási hiba 0/100 165ms 102308 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))
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Futási hiba 90ms 89308 KiB
2 Futási hiba 140ms 95668 KiB
subtask2 0/8
3 Futási hiba 141ms 96244 KiB
4 Futási hiba 134ms 96212 KiB
5 Futási hiba 141ms 96536 KiB
6 Futási hiba 141ms 96936 KiB
7 Futási hiba 133ms 97288 KiB
subtask3 0/15
8 Futási hiba 87ms 91372 KiB
9 Futási hiba 82ms 91480 KiB
10 Futási hiba 89ms 91724 KiB
11 Futási hiba 82ms 91808 KiB
12 Futási hiba 92ms 92032 KiB
13 Futási hiba 82ms 92436 KiB
14 Futási hiba 89ms 92312 KiB
15 Futási hiba 89ms 92224 KiB
16 Futási hiba 89ms 92736 KiB
17 Futási hiba 90ms 92932 KiB
18 Futási hiba 90ms 92944 KiB
subtask4 0/34
19 Futási hiba 165ms 99056 KiB
20 Futási hiba 138ms 99100 KiB
21 Futási hiba 164ms 99652 KiB
22 Futási hiba 148ms 99168 KiB
23 Futási hiba 140ms 99016 KiB
24 Futási hiba 146ms 99164 KiB
25 Futási hiba 140ms 99588 KiB
26 Futási hiba 146ms 99708 KiB
27 Futási hiba 164ms 101316 KiB
28 Futási hiba 143ms 98796 KiB
29 Futási hiba 136ms 99376 KiB
30 Futási hiba 130ms 99308 KiB
31 Futási hiba 130ms 99352 KiB
32 Futási hiba 136ms 100208 KiB
33 Futási hiba 164ms 100392 KiB
subtask5 0/21
34 Futási hiba 114ms 94904 KiB
35 Futási hiba 125ms 97624 KiB
36 Futási hiba 130ms 97424 KiB
37 Futási hiba 130ms 97592 KiB
38 Futási hiba 125ms 97288 KiB
39 Futási hiba 130ms 97524 KiB
40 Futási hiba 123ms 97252 KiB
41 Futási hiba 119ms 97204 KiB
42 Futási hiba 101ms 93836 KiB
43 Futási hiba 94ms 93600 KiB
44 Futási hiba 100ms 93552 KiB
45 Futási hiba 93ms 93644 KiB
46 Futási hiba 90ms 93536 KiB
47 Futási hiba 90ms 93620 KiB
48 Futási hiba 112ms 94604 KiB
49 Futási hiba 105ms 94412 KiB
subtask6 0/22
50 Futási hiba 136ms 100024 KiB
51 Futási hiba 146ms 100164 KiB
52 Futási hiba 164ms 99692 KiB
53 Futási hiba 148ms 100560 KiB
54 Futási hiba 149ms 100176 KiB
55 Futási hiba 140ms 99948 KiB
56 Futási hiba 160ms 102308 KiB
57 Futási hiba 160ms 102072 KiB
58 Futási hiba 103ms 94392 KiB
59 Futási hiba 130ms 99872 KiB
60 Futási hiba 143ms 99640 KiB
61 Futási hiba 136ms 99556 KiB
62 Futási hiba 143ms 100112 KiB
63 Futási hiba 136ms 100084 KiB
64 Futási hiba 149ms 99660 KiB
65 Futási hiba 149ms 100360 KiB
66 Futási hiba 142ms 99888 KiB