100152024-03-24 09:55:11111Autópálya inflációpypy3Futási hiba 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))
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Futási hiba90ms89308 KiB
2Futási hiba140ms95668 KiB
subtask20/8
3Futási hiba141ms96244 KiB
4Futási hiba134ms96212 KiB
5Futási hiba141ms96536 KiB
6Futási hiba141ms96936 KiB
7Futási hiba133ms97288 KiB
subtask30/15
8Futási hiba87ms91372 KiB
9Futási hiba82ms91480 KiB
10Futási hiba89ms91724 KiB
11Futási hiba82ms91808 KiB
12Futási hiba92ms92032 KiB
13Futási hiba82ms92436 KiB
14Futási hiba89ms92312 KiB
15Futási hiba89ms92224 KiB
16Futási hiba89ms92736 KiB
17Futási hiba90ms92932 KiB
18Futási hiba90ms92944 KiB
subtask40/34
19Futási hiba165ms99056 KiB
20Futási hiba138ms99100 KiB
21Futási hiba164ms99652 KiB
22Futási hiba148ms99168 KiB
23Futási hiba140ms99016 KiB
24Futási hiba146ms99164 KiB
25Futási hiba140ms99588 KiB
26Futási hiba146ms99708 KiB
27Futási hiba164ms101316 KiB
28Futási hiba143ms98796 KiB
29Futási hiba136ms99376 KiB
30Futási hiba130ms99308 KiB
31Futási hiba130ms99352 KiB
32Futási hiba136ms100208 KiB
33Futási hiba164ms100392 KiB
subtask50/21
34Futási hiba114ms94904 KiB
35Futási hiba125ms97624 KiB
36Futási hiba130ms97424 KiB
37Futási hiba130ms97592 KiB
38Futási hiba125ms97288 KiB
39Futási hiba130ms97524 KiB
40Futási hiba123ms97252 KiB
41Futási hiba119ms97204 KiB
42Futási hiba101ms93836 KiB
43Futási hiba94ms93600 KiB
44Futási hiba100ms93552 KiB
45Futási hiba93ms93644 KiB
46Futási hiba90ms93536 KiB
47Futási hiba90ms93620 KiB
48Futási hiba112ms94604 KiB
49Futási hiba105ms94412 KiB
subtask60/22
50Futási hiba136ms100024 KiB
51Futási hiba146ms100164 KiB
52Futási hiba164ms99692 KiB
53Futási hiba148ms100560 KiB
54Futási hiba149ms100176 KiB
55Futási hiba140ms99948 KiB
56Futási hiba160ms102308 KiB
57Futási hiba160ms102072 KiB
58Futási hiba103ms94392 KiB
59Futási hiba130ms99872 KiB
60Futási hiba143ms99640 KiB
61Futási hiba136ms99556 KiB
62Futási hiba143ms100112 KiB
63Futási hiba136ms100084 KiB
64Futási hiba149ms99660 KiB
65Futási hiba149ms100360 KiB
66Futási hiba142ms99888 KiB