Beküldés #19 113

19113

2025-11-24 19:26:59

python3

Időlimit túllépés 65/80

1.1s

10628 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		Összpont	Teszt	Verdikt	Idő	Memória
	subtask1	0/0
	subtask1	0/0	1	Elfogadva	16ms	3232 KiB
	subtask2	20/20
			2	Elfogadva	16ms	3312 KiB
			3	Elfogadva	17ms	3108 KiB
			4	Elfogadva	17ms	3120 KiB
			5	Elfogadva	37ms	5008 KiB
			6	Elfogadva	25ms	3912 KiB
			7	Elfogadva	54ms	6316 KiB
			8	Elfogadva	54ms	6392 KiB
			9	Elfogadva	16ms	3144 KiB
			10	Elfogadva	79ms	8412 KiB
			11	Elfogadva	16ms	3124 KiB
			12	Elfogadva	16ms	3204 KiB
	subtask3	25/25
			13	Elfogadva	17ms	3212 KiB
			14	Elfogadva	17ms	3124 KiB
			15	Elfogadva	17ms	3120 KiB
			16	Elfogadva	17ms	3124 KiB
			17	Elfogadva	17ms	3080 KiB
			18	Elfogadva	17ms	3312 KiB
			19	Elfogadva	16ms	3324 KiB
			20	Elfogadva	17ms	3320 KiB
			21	Elfogadva	17ms	3032 KiB
			22	Elfogadva	92ms	3408 KiB
			23	Elfogadva	19ms	3620 KiB
			24	Elfogadva	52ms	3548 KiB
			25	Elfogadva	25ms	3384 KiB
			26	Elfogadva	21ms	3380 KiB
			27	Elfogadva	28ms	3608 KiB
			28	Elfogadva	303ms	6424 KiB
			29	Elfogadva	32ms	4080 KiB
			30	Elfogadva	141ms	7332 KiB
			31	Elfogadva	70ms	6076 KiB
			32	Elfogadva	128ms	7476 KiB
			33	Elfogadva	50ms	6900 KiB
	subtask4	20/20
			34	Elfogadva	17ms	3128 KiB
			35	Elfogadva	17ms	3320 KiB
			36	Elfogadva	16ms	3320 KiB
			37	Elfogadva	17ms	3120 KiB
			38	Elfogadva	17ms	3312 KiB
			39	Elfogadva	17ms	3164 KiB
			40	Elfogadva	17ms	3312 KiB
			41	Elfogadva	17ms	3124 KiB
			42	Elfogadva	17ms	3284 KiB
			43	Elfogadva	16ms	3124 KiB
			44	Elfogadva	16ms	3124 KiB
			45	Elfogadva	17ms	3124 KiB
			46	Elfogadva	17ms	3220 KiB
			47	Elfogadva	17ms	3124 KiB
			48	Elfogadva	17ms	3260 KiB
			49	Elfogadva	17ms	3288 KiB
			50	Elfogadva	17ms	3436 KiB
			51	Elfogadva	17ms	3568 KiB
			52	Elfogadva	17ms	3116 KiB
			53	Elfogadva	16ms	3076 KiB
			54	Elfogadva	17ms	3052 KiB
			55	Elfogadva	16ms	3060 KiB
			56	Elfogadva	16ms	3148 KiB
			57	Elfogadva	17ms	3124 KiB
			58	Elfogadva	17ms	3124 KiB
			59	Elfogadva	17ms	3148 KiB
			60	Elfogadva	17ms	3120 KiB
			61	Elfogadva	17ms	3124 KiB
			62	Elfogadva	17ms	3144 KiB
			63	Elfogadva	16ms	3120 KiB
			64	Elfogadva	16ms	3120 KiB
			65	Elfogadva	16ms	3120 KiB
			66	Elfogadva	16ms	3320 KiB
	subtask5	0/15
			67	Elfogadva	17ms	3128 KiB
			68	Elfogadva	16ms	3312 KiB
			69	Elfogadva	17ms	3108 KiB
			70	Elfogadva	17ms	3120 KiB
			71	Elfogadva	37ms	5008 KiB
			72	Elfogadva	25ms	3912 KiB
			73	Elfogadva	54ms	6316 KiB
			74	Elfogadva	54ms	6392 KiB
			75	Elfogadva	16ms	3144 KiB
			76	Elfogadva	79ms	8412 KiB
			77	Elfogadva	16ms	3124 KiB
			78	Elfogadva	16ms	3204 KiB
			79	Elfogadva	17ms	3212 KiB
			80	Elfogadva	17ms	3124 KiB
			81	Elfogadva	17ms	3120 KiB
			82	Elfogadva	17ms	3124 KiB
			83	Elfogadva	17ms	3080 KiB
			84	Elfogadva	17ms	3312 KiB
			85	Elfogadva	16ms	3324 KiB
			86	Elfogadva	17ms	3320 KiB
			87	Elfogadva	17ms	3032 KiB
			88	Elfogadva	92ms	3408 KiB
			89	Elfogadva	19ms	3620 KiB
			90	Elfogadva	52ms	3548 KiB
			91	Elfogadva	25ms	3384 KiB
			92	Elfogadva	21ms	3380 KiB
			93	Elfogadva	28ms	3608 KiB
			94	Elfogadva	303ms	6424 KiB
			95	Elfogadva	32ms	4080 KiB
			96	Elfogadva	141ms	7332 KiB
			97	Elfogadva	70ms	6076 KiB
			98	Elfogadva	128ms	7476 KiB
			99	Elfogadva	50ms	6900 KiB
			100	Elfogadva	17ms	3320 KiB
			101	Elfogadva	16ms	3320 KiB
			102	Elfogadva	17ms	3120 KiB
			103	Elfogadva	17ms	3312 KiB
			104	Elfogadva	17ms	3164 KiB
			105	Elfogadva	17ms	3312 KiB
			106	Elfogadva	17ms	3124 KiB
			107	Elfogadva	17ms	3284 KiB
			108	Elfogadva	16ms	3124 KiB
			109	Elfogadva	16ms	3124 KiB
			110	Elfogadva	17ms	3124 KiB
			111	Elfogadva	17ms	3220 KiB
			112	Elfogadva	17ms	3124 KiB
			113	Elfogadva	17ms	3260 KiB
			114	Elfogadva	17ms	3288 KiB
			115	Elfogadva	17ms	3436 KiB
			116	Elfogadva	17ms	3568 KiB
			117	Elfogadva	17ms	3116 KiB
			118	Elfogadva	16ms	3076 KiB
			119	Elfogadva	17ms	3052 KiB
			120	Elfogadva	16ms	3060 KiB
			121	Elfogadva	16ms	3148 KiB
			122	Elfogadva	17ms	3124 KiB
			123	Elfogadva	17ms	3124 KiB
			124	Elfogadva	17ms	3148 KiB
			125	Elfogadva	17ms	3120 KiB
			126	Elfogadva	17ms	3124 KiB
			127	Elfogadva	17ms	3144 KiB
			128	Elfogadva	16ms	3120 KiB
			129	Elfogadva	16ms	3120 KiB
130	Elfogadva		16ms	3120 KiB
131	Elfogadva		16ms	3320 KiB
132	Elfogadva		67ms	3240 KiB
133	Elfogadva		18ms	3636 KiB
134	Elfogadva		46ms	3424 KiB
135	Elfogadva		25ms	3296 KiB
136	Elfogadva		32ms	3384 KiB
137	Elfogadva		24ms	3352 KiB
138	Elfogadva		57ms	3128 KiB
139	Elfogadva		21ms	3520 KiB
140	Elfogadva		37ms	4824 KiB
141	Elfogadva		28ms	3956 KiB
142	Elfogadva		61ms	6308 KiB
143	Elfogadva		83ms	6560 KiB
144	Elfogadva		67ms	7416 KiB
145	Elfogadva		59ms	6304 KiB
146	Elfogadva		119ms	10628 KiB
147	Elfogadva		717ms	9124 KiB
148	Időlimit túllépés		1.1s	7112 KiB
149	Időlimit túllépés		1.098s	5152 KiB