191122025-11-24 19:24:15birozsVárosnézéspypy3Időlimit túllépés 65/801.103s34700 KiB
class Ter:
    def __init__(self,Nev,Latni,Hossz,Honnan):
        self.Nev = Nev
        self.Latni = Latni
        self.Hossz = Hossz
        self.Honnan = Honnan
        pass
    def kiir(self):
        return print(self.Nev,self.Latni,self.Hossz,self.Honnan)
    
N,M = map(int,input().split())
L = list(map(int,input().split()))
Bit = [Ter(0,0,0,0)]
for i in range(1,N+1):
    Bit.append(Ter(i,L[i-1],L[i-1],0))
Utak = {}
for _ in range(M):
    A,B = map(int,input().split())
    if A not in Utak:
        Utak[A] = [B]
    else:
        Utak[A].append(B)
sor = [Bit[1]]
maxhossz = 0
while len(sor) != 0:
    AktTer = sor.pop()
    if AktTer.Nev == N:
        if AktTer.Hossz > maxhossz:
            maxhossz = AktTer.Hossz
            honnan = AktTer.Honnan
            utvonal = str(AktTer.Nev)
            while honnan != 0:
                utvonal = str(honnan) + " " + utvonal
                honnan = Bit[honnan].Honnan
    if AktTer.Nev in Utak:
        for Hova in Utak[AktTer.Nev]:
            if Bit[Hova].Hossz < AktTer.Hossz + Bit[Hova].Latni:
                Bit[Hova].Hossz = AktTer.Hossz + Bit[Hova].Latni
                Bit[Hova].Honnan = AktTer.Nev
                sor.append(Bit[Hova])
if maxhossz != 0:
    print(maxhossz)
    print(utvonal)
else:
    print(-1)
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva39ms19692 KiB
subtask220/20
2Elfogadva39ms19692 KiB
3Elfogadva45ms19640 KiB
4Elfogadva45ms19712 KiB
5Elfogadva104ms24080 KiB
6Elfogadva93ms23500 KiB
7Elfogadva130ms24328 KiB
8Elfogadva104ms24040 KiB
9Elfogadva43ms21228 KiB
10Elfogadva119ms27256 KiB
11Elfogadva43ms21040 KiB
12Elfogadva39ms19872 KiB
subtask325/25
13Elfogadva43ms19664 KiB
14Elfogadva45ms19624 KiB
15Elfogadva41ms19712 KiB
16Elfogadva48ms21160 KiB
17Elfogadva48ms19920 KiB
18Elfogadva50ms21196 KiB
19Elfogadva45ms21208 KiB
20Elfogadva43ms21072 KiB
21Elfogadva41ms19840 KiB
22Elfogadva101ms22248 KiB
23Elfogadva59ms21936 KiB
24Elfogadva103ms22220 KiB
25Elfogadva86ms22052 KiB
26Elfogadva79ms22716 KiB
27Elfogadva82ms22728 KiB
28Elfogadva160ms25140 KiB
29Elfogadva101ms23268 KiB
30Elfogadva128ms25188 KiB
31Elfogadva93ms23780 KiB
32Elfogadva118ms24296 KiB
33Elfogadva86ms25316 KiB
subtask420/20
34Elfogadva39ms19680 KiB
35Elfogadva43ms19776 KiB
36Elfogadva46ms19608 KiB
37Elfogadva39ms19664 KiB
38Elfogadva52ms21248 KiB
39Elfogadva46ms19712 KiB
40Elfogadva46ms21216 KiB
41Elfogadva43ms21036 KiB
42Elfogadva43ms21200 KiB
43Elfogadva45ms19692 KiB
44Elfogadva46ms21184 KiB
45Elfogadva48ms19688 KiB
46Elfogadva59ms21372 KiB
47Elfogadva46ms21188 KiB
48Elfogadva52ms21140 KiB
49Elfogadva59ms21548 KiB
50Elfogadva46ms19692 KiB
51Elfogadva39ms19828 KiB
52Elfogadva39ms19656 KiB
53Elfogadva45ms19692 KiB
54Elfogadva39ms19692 KiB
55Elfogadva45ms19692 KiB
56Elfogadva39ms20008 KiB
57Elfogadva45ms19692 KiB
58Elfogadva48ms19792 KiB
59Elfogadva46ms19880 KiB
60Elfogadva43ms19600 KiB
61Elfogadva39ms19640 KiB
62Elfogadva46ms19948 KiB
63Elfogadva41ms19828 KiB
64Elfogadva39ms19872 KiB
65Elfogadva45ms19696 KiB
66Elfogadva50ms21228 KiB
subtask50/15
67Elfogadva39ms19680 KiB
68Elfogadva39ms19692 KiB
69Elfogadva45ms19640 KiB
70Elfogadva45ms19712 KiB
71Elfogadva104ms24080 KiB
72Elfogadva93ms23500 KiB
73Elfogadva130ms24328 KiB
74Elfogadva104ms24040 KiB
75Elfogadva43ms21228 KiB
76Elfogadva119ms27256 KiB
77Elfogadva43ms21040 KiB
78Elfogadva39ms19872 KiB
79Elfogadva43ms19664 KiB
80Elfogadva45ms19624 KiB
81Elfogadva41ms19712 KiB
82Elfogadva48ms21160 KiB
83Elfogadva48ms19920 KiB
84Elfogadva50ms21196 KiB
85Elfogadva45ms21208 KiB
86Elfogadva43ms21072 KiB
87Elfogadva41ms19840 KiB
88Elfogadva101ms22248 KiB
89Elfogadva59ms21936 KiB
90Elfogadva103ms22220 KiB
91Elfogadva86ms22052 KiB
92Elfogadva79ms22716 KiB
93Elfogadva82ms22728 KiB
94Elfogadva160ms25140 KiB
95Elfogadva101ms23268 KiB
96Elfogadva128ms25188 KiB
97Elfogadva93ms23780 KiB
98Elfogadva118ms24296 KiB
99Elfogadva86ms25316 KiB
100Elfogadva43ms19776 KiB
101Elfogadva46ms19608 KiB
102Elfogadva39ms19664 KiB
103Elfogadva52ms21248 KiB
104Elfogadva46ms19712 KiB
105Elfogadva46ms21216 KiB
106Elfogadva43ms21036 KiB
107Elfogadva43ms21200 KiB
108Elfogadva45ms19692 KiB
109Elfogadva46ms21184 KiB
110Elfogadva48ms19688 KiB
111Elfogadva59ms21372 KiB
112Elfogadva46ms21188 KiB
113Elfogadva52ms21140 KiB
114Elfogadva59ms21548 KiB
115Elfogadva46ms19692 KiB
116Elfogadva39ms19828 KiB
117Elfogadva39ms19656 KiB
118Elfogadva45ms19692 KiB
119Elfogadva39ms19692 KiB
120Elfogadva45ms19692 KiB
121Elfogadva39ms20008 KiB
122Elfogadva45ms19692 KiB
123Elfogadva48ms19792 KiB
124Elfogadva46ms19880 KiB
125Elfogadva43ms19600 KiB
126Elfogadva39ms19640 KiB
127Elfogadva46ms19948 KiB
128Elfogadva41ms19828 KiB
129Elfogadva39ms19872 KiB
130Elfogadva45ms19696 KiB
131Elfogadva50ms21228 KiB
132Elfogadva108ms22448 KiB
133Elfogadva64ms21980 KiB
134Elfogadva90ms22160 KiB
135Elfogadva85ms22180 KiB
136Elfogadva98ms22144 KiB
137Elfogadva93ms21988 KiB
138Elfogadva96ms22212 KiB
139Elfogadva78ms22816 KiB
140Elfogadva105ms23796 KiB
141Elfogadva100ms23268 KiB
142Elfogadva115ms24648 KiB
143Elfogadva112ms24620 KiB
144Elfogadva111ms26144 KiB
145Elfogadva122ms24456 KiB
146Elfogadva135ms28284 KiB
147Elfogadva412ms31252 KiB
148Időlimit túllépés1.085s32744 KiB
149Időlimit túllépés1.103s34700 KiB