Beküldés #19 114

19114

2025-11-24 19:45:40

python3

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

1.1s

8084 KiB

N,M = map(int,input().split())
L = list(map(int,input().split()))
Honnan = [0] * (N+1)
Hossz = [0] * (N+1)
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 = [[1,L[0]]]
Hossz[1] = L[0]
maxhossz = 0
while len(sor) != 0:
    akt = sor.pop()
    aktter = akt[0]
    akthossz = akt[1]
    if aktter == N:
        if akthossz > maxhossz:
            maxhossz = akthossz
            honnan = Honnan[aktter]
            utvonal = str(aktter)
            while honnan != 0:
                utvonal = str(honnan) + " " + utvonal
                honnan = Honnan[honnan]
    if aktter in Utak:
        for Hova in Utak[aktter]:
            if Hossz[Hova] < akthossz + L[Hova-1]:
                sor.append([Hova,akthossz + L[Hova-1]])
                Honnan[Hova] = aktter
                Hossz[Hova] = akthossz + L[Hova-1]
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	17ms	3320 KiB
	subtask2	20/20
			2	Elfogadva	16ms	3060 KiB
			3	Elfogadva	17ms	3124 KiB
			4	Elfogadva	16ms	3388 KiB
			5	Elfogadva	34ms	4396 KiB
			6	Elfogadva	24ms	3636 KiB
			7	Elfogadva	46ms	5280 KiB
			8	Elfogadva	46ms	5284 KiB
			9	Elfogadva	16ms	3084 KiB
			10	Elfogadva	70ms	6776 KiB
			11	Elfogadva	16ms	3120 KiB
			12	Elfogadva	14ms	3124 KiB
	subtask3	25/25
			13	Elfogadva	16ms	3312 KiB
			14	Elfogadva	16ms	3124 KiB
			15	Elfogadva	16ms	3200 KiB
			16	Elfogadva	17ms	3124 KiB
			17	Elfogadva	17ms	3080 KiB
			18	Elfogadva	17ms	3208 KiB
			19	Elfogadva	16ms	3124 KiB
			20	Elfogadva	16ms	3212 KiB
			21	Elfogadva	17ms	3120 KiB
			22	Elfogadva	94ms	3320 KiB
			23	Elfogadva	17ms	3464 KiB
			24	Elfogadva	57ms	3508 KiB
			25	Elfogadva	26ms	3380 KiB
			26	Elfogadva	20ms	3424 KiB
			27	Elfogadva	28ms	3492 KiB
			28	Elfogadva	323ms	5636 KiB
			29	Elfogadva	32ms	3816 KiB
			30	Elfogadva	135ms	6196 KiB
			31	Elfogadva	61ms	5056 KiB
			32	Elfogadva	123ms	6152 KiB
			33	Elfogadva	32ms	5632 KiB
	subtask4	20/20
			34	Elfogadva	16ms	3204 KiB
			35	Elfogadva	17ms	3124 KiB
			36	Elfogadva	16ms	3124 KiB
			37	Elfogadva	17ms	3320 KiB
			38	Elfogadva	17ms	3192 KiB
			39	Elfogadva	16ms	3008 KiB
			40	Elfogadva	17ms	3220 KiB
			41	Elfogadva	16ms	3076 KiB
			42	Elfogadva	17ms	3000 KiB
			43	Elfogadva	16ms	3136 KiB
			44	Elfogadva	17ms	3016 KiB
			45	Elfogadva	16ms	3212 KiB
			46	Elfogadva	17ms	3320 KiB
			47	Elfogadva	17ms	3140 KiB
			48	Elfogadva	17ms	3104 KiB
			49	Elfogadva	18ms	3124 KiB
			50	Elfogadva	16ms	3112 KiB
			51	Elfogadva	17ms	3224 KiB
			52	Elfogadva	16ms	3204 KiB
			53	Elfogadva	17ms	3124 KiB
			54	Elfogadva	17ms	3124 KiB
			55	Elfogadva	17ms	3136 KiB
			56	Elfogadva	17ms	3124 KiB
			57	Elfogadva	16ms	3128 KiB
			58	Elfogadva	17ms	3208 KiB
			59	Elfogadva	16ms	3220 KiB
			60	Elfogadva	17ms	3228 KiB
			61	Elfogadva	16ms	3024 KiB
			62	Elfogadva	16ms	3356 KiB
			63	Elfogadva	16ms	3128 KiB
			64	Elfogadva	16ms	3136 KiB
			65	Elfogadva	16ms	3120 KiB
			66	Elfogadva	16ms	3020 KiB
	subtask5	0/15
			67	Elfogadva	16ms	3204 KiB
			68	Elfogadva	16ms	3060 KiB
			69	Elfogadva	17ms	3124 KiB
			70	Elfogadva	16ms	3388 KiB
			71	Elfogadva	34ms	4396 KiB
			72	Elfogadva	24ms	3636 KiB
			73	Elfogadva	46ms	5280 KiB
			74	Elfogadva	46ms	5284 KiB
			75	Elfogadva	16ms	3084 KiB
			76	Elfogadva	70ms	6776 KiB
			77	Elfogadva	16ms	3120 KiB
			78	Elfogadva	14ms	3124 KiB
			79	Elfogadva	16ms	3312 KiB
			80	Elfogadva	16ms	3124 KiB
			81	Elfogadva	16ms	3200 KiB
			82	Elfogadva	17ms	3124 KiB
			83	Elfogadva	17ms	3080 KiB
			84	Elfogadva	17ms	3208 KiB
			85	Elfogadva	16ms	3124 KiB
			86	Elfogadva	16ms	3212 KiB
			87	Elfogadva	17ms	3120 KiB
			88	Elfogadva	94ms	3320 KiB
			89	Elfogadva	17ms	3464 KiB
			90	Elfogadva	57ms	3508 KiB
			91	Elfogadva	26ms	3380 KiB
			92	Elfogadva	20ms	3424 KiB
			93	Elfogadva	28ms	3492 KiB
			94	Elfogadva	323ms	5636 KiB
			95	Elfogadva	32ms	3816 KiB
			96	Elfogadva	135ms	6196 KiB
			97	Elfogadva	61ms	5056 KiB
			98	Elfogadva	123ms	6152 KiB
			99	Elfogadva	32ms	5632 KiB
			100	Elfogadva	17ms	3124 KiB
			101	Elfogadva	16ms	3124 KiB
			102	Elfogadva	17ms	3320 KiB
			103	Elfogadva	17ms	3192 KiB
			104	Elfogadva	16ms	3008 KiB
			105	Elfogadva	17ms	3220 KiB
			106	Elfogadva	16ms	3076 KiB
			107	Elfogadva	17ms	3000 KiB
			108	Elfogadva	16ms	3136 KiB
			109	Elfogadva	17ms	3016 KiB
			110	Elfogadva	16ms	3212 KiB
			111	Elfogadva	17ms	3320 KiB
			112	Elfogadva	17ms	3140 KiB
			113	Elfogadva	17ms	3104 KiB
			114	Elfogadva	18ms	3124 KiB
			115	Elfogadva	16ms	3112 KiB
			116	Elfogadva	17ms	3224 KiB
			117	Elfogadva	16ms	3204 KiB
			118	Elfogadva	17ms	3124 KiB
			119	Elfogadva	17ms	3124 KiB
			120	Elfogadva	17ms	3136 KiB
			121	Elfogadva	17ms	3124 KiB
			122	Elfogadva	16ms	3128 KiB
			123	Elfogadva	17ms	3208 KiB
			124	Elfogadva	16ms	3220 KiB
			125	Elfogadva	17ms	3228 KiB
			126	Elfogadva	16ms	3024 KiB
			127	Elfogadva	16ms	3356 KiB
			128	Elfogadva	16ms	3128 KiB
			129	Elfogadva	16ms	3136 KiB
130	Elfogadva		16ms	3120 KiB
131	Elfogadva		16ms	3020 KiB
132	Elfogadva		71ms	3312 KiB
133	Elfogadva		17ms	3380 KiB
134	Elfogadva		48ms	3380 KiB
135	Elfogadva		24ms	3352 KiB
136	Elfogadva		32ms	3380 KiB
137	Elfogadva		24ms	3124 KiB
138	Elfogadva		57ms	3296 KiB
139	Elfogadva		19ms	3380 KiB
140	Elfogadva		35ms	4312 KiB
141	Elfogadva		26ms	3708 KiB
142	Elfogadva		50ms	5288 KiB
143	Elfogadva		79ms	5496 KiB
144	Elfogadva		59ms	5920 KiB
145	Elfogadva		54ms	5136 KiB
146	Elfogadva		108ms	8084 KiB
147	Elfogadva		750ms	7292 KiB
148	Időlimit túllépés		1.1s	5988 KiB
149	Időlimit túllépés		1.1s	4440 KiB