154552025-02-19 17:17:51AblablablaAutópálya inflációpypy3Futási hiba 15/100782ms131072 KiB
import sys
import heapq
from decimal import Decimal, getcontext

INF = -1
MOD = int(1e9 + 7)

n, m = map(int, input().split())

csucsok = [[] for _ in range(n)]
hossz = [[] for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1

    csucsok[a].append(b)
    hossz[a].append(c)
    csucsok[b].append(a)
    hossz[b].append(c)

class Comp:
    def __init__(self, ans, mely):
        self.ans = ans
        self.mely = mely

    def __call__(self, a, b):
        if self.ans[a] == self.ans[b]:
            return self.mely[a] > self.mely[b]
        return self.ans[a] > self.ans[b]

bejar = []
ans = [INF] * n
ans[0] = 0
heapq.heappush(bejar, (ans[0], 0))
bejart = [False] * n
opciok = [[INF] * (n + 2) for _ in range(n)]
opciok[0][1] = 0
mely = [0] * n

while bejar:
    akt = heapq.heappop(bejar)[1]

    if bejart[akt]:
        continue

    #print(akt);

    bejart[akt] = True

    for i in range(len(csucsok[akt])):
        kovi = csucsok[akt][i]
        suly = hossz[akt][i]

        if bejart[kovi]:
            continue

        for j in range(1, n + 1):
            if opciok[akt][j] == -1:
                continue

            tav = opciok[akt][j] + suly * int(1 << (j - 1))

            if(opciok[kovi][j + 1]) == -1:
                opciok[kovi][j + 1] = tav;
            else:
                opciok[kovi][j + 1] = int(min(int(opciok[kovi][j + 1]), int(tav)))

            if ans[kovi] > tav or ans[kovi] == -1:
                mely[kovi] = j + 1
                ans[kovi] = int(tav);
            

        heapq.heappush(bejar, (int(ans[kovi]), kovi))

for i in range(1, n):
    print(ans[i] % MOD)
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva78ms24228 KiB
2Futási hiba782ms131072 KiB
subtask20/8
3Elfogadva370ms98404 KiB
4Elfogadva351ms104912 KiB
5Futási hiba527ms131072 KiB
6Elfogadva312ms98484 KiB
7Futási hiba344ms131072 KiB
subtask315/15
8Elfogadva86ms23732 KiB
9Elfogadva79ms23920 KiB
10Elfogadva87ms23712 KiB
11Elfogadva79ms24052 KiB
12Elfogadva89ms23708 KiB
13Elfogadva89ms23868 KiB
14Elfogadva81ms23864 KiB
15Elfogadva81ms23736 KiB
16Elfogadva87ms23732 KiB
17Elfogadva79ms23736 KiB
18Elfogadva86ms23840 KiB
subtask40/34
19Elfogadva451ms100160 KiB
20Futási hiba643ms131072 KiB
21Futási hiba621ms131072 KiB
22Elfogadva442ms99176 KiB
23Elfogadva430ms99044 KiB
24Futási hiba635ms131072 KiB
25Elfogadva446ms99560 KiB
26Elfogadva507ms100144 KiB
27Futási hiba504ms131072 KiB
28Futási hiba458ms131072 KiB
29Futási hiba492ms131072 KiB
30Elfogadva497ms131008 KiB
31Elfogadva556ms130280 KiB
32Futási hiba600ms131072 KiB
33Futási hiba601ms131072 KiB
subtask50/21
34Elfogadva155ms28708 KiB
35Hibás válasz296ms31712 KiB
36Hibás válasz195ms27300 KiB
37Hibás válasz201ms28120 KiB
38Elfogadva189ms27620 KiB
39Elfogadva200ms27772 KiB
40Elfogadva407ms42904 KiB
41Elfogadva377ms41448 KiB
42Elfogadva119ms27632 KiB
43Elfogadva127ms27644 KiB
44Elfogadva115ms27880 KiB
45Elfogadva129ms27836 KiB
46Elfogadva134ms27624 KiB
47Elfogadva115ms26936 KiB
48Elfogadva152ms27628 KiB
49Elfogadva166ms28012 KiB
subtask60/22
50Futási hiba522ms131072 KiB
51Futási hiba623ms131072 KiB
52Hibás válasz446ms99460 KiB
53Hibás válasz407ms99508 KiB
54Elfogadva407ms99808 KiB
55Elfogadva442ms99048 KiB
56Futási hiba513ms131072 KiB
57Futási hiba583ms131072 KiB
58Elfogadva163ms40596 KiB
59Futási hiba467ms131072 KiB
60Futási hiba472ms131072 KiB
61Futási hiba490ms131072 KiB
62Futási hiba503ms131072 KiB
63Futási hiba560ms131072 KiB
64Futási hiba593ms131072 KiB
65Futási hiba584ms131072 KiB
66Futási hiba593ms131072 KiB