Submission #19,114

19114

2025-11-24 19:45:40

python3

Time limit exceeded 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)

Subtask		Sum	Test	Verdict	Time	Memory
	subtask1	0/0
	subtask1	0/0	1	Accepted	17ms	3320 KiB
	subtask2	20/20
			2	Accepted	16ms	3060 KiB
			3	Accepted	17ms	3124 KiB
			4	Accepted	16ms	3388 KiB
			5	Accepted	34ms	4396 KiB
			6	Accepted	24ms	3636 KiB
			7	Accepted	46ms	5280 KiB
			8	Accepted	46ms	5284 KiB
			9	Accepted	16ms	3084 KiB
			10	Accepted	70ms	6776 KiB
			11	Accepted	16ms	3120 KiB
			12	Accepted	14ms	3124 KiB
	subtask3	25/25
			13	Accepted	16ms	3312 KiB
			14	Accepted	16ms	3124 KiB
			15	Accepted	16ms	3200 KiB
			16	Accepted	17ms	3124 KiB
			17	Accepted	17ms	3080 KiB
			18	Accepted	17ms	3208 KiB
			19	Accepted	16ms	3124 KiB
			20	Accepted	16ms	3212 KiB
			21	Accepted	17ms	3120 KiB
			22	Accepted	94ms	3320 KiB
			23	Accepted	17ms	3464 KiB
			24	Accepted	57ms	3508 KiB
			25	Accepted	26ms	3380 KiB
			26	Accepted	20ms	3424 KiB
			27	Accepted	28ms	3492 KiB
			28	Accepted	323ms	5636 KiB
			29	Accepted	32ms	3816 KiB
			30	Accepted	135ms	6196 KiB
			31	Accepted	61ms	5056 KiB
			32	Accepted	123ms	6152 KiB
			33	Accepted	32ms	5632 KiB
	subtask4	20/20
			34	Accepted	16ms	3204 KiB
			35	Accepted	17ms	3124 KiB
			36	Accepted	16ms	3124 KiB
			37	Accepted	17ms	3320 KiB
			38	Accepted	17ms	3192 KiB
			39	Accepted	16ms	3008 KiB
			40	Accepted	17ms	3220 KiB
			41	Accepted	16ms	3076 KiB
			42	Accepted	17ms	3000 KiB
			43	Accepted	16ms	3136 KiB
			44	Accepted	17ms	3016 KiB
			45	Accepted	16ms	3212 KiB
			46	Accepted	17ms	3320 KiB
			47	Accepted	17ms	3140 KiB
			48	Accepted	17ms	3104 KiB
			49	Accepted	18ms	3124 KiB
			50	Accepted	16ms	3112 KiB
			51	Accepted	17ms	3224 KiB
			52	Accepted	16ms	3204 KiB
			53	Accepted	17ms	3124 KiB
			54	Accepted	17ms	3124 KiB
			55	Accepted	17ms	3136 KiB
			56	Accepted	17ms	3124 KiB
			57	Accepted	16ms	3128 KiB
			58	Accepted	17ms	3208 KiB
			59	Accepted	16ms	3220 KiB
			60	Accepted	17ms	3228 KiB
			61	Accepted	16ms	3024 KiB
			62	Accepted	16ms	3356 KiB
			63	Accepted	16ms	3128 KiB
			64	Accepted	16ms	3136 KiB
			65	Accepted	16ms	3120 KiB
			66	Accepted	16ms	3020 KiB
	subtask5	0/15
			67	Accepted	16ms	3204 KiB
			68	Accepted	16ms	3060 KiB
			69	Accepted	17ms	3124 KiB
			70	Accepted	16ms	3388 KiB
			71	Accepted	34ms	4396 KiB
			72	Accepted	24ms	3636 KiB
			73	Accepted	46ms	5280 KiB
			74	Accepted	46ms	5284 KiB
			75	Accepted	16ms	3084 KiB
			76	Accepted	70ms	6776 KiB
			77	Accepted	16ms	3120 KiB
			78	Accepted	14ms	3124 KiB
			79	Accepted	16ms	3312 KiB
			80	Accepted	16ms	3124 KiB
			81	Accepted	16ms	3200 KiB
			82	Accepted	17ms	3124 KiB
			83	Accepted	17ms	3080 KiB
			84	Accepted	17ms	3208 KiB
			85	Accepted	16ms	3124 KiB
			86	Accepted	16ms	3212 KiB
			87	Accepted	17ms	3120 KiB
			88	Accepted	94ms	3320 KiB
			89	Accepted	17ms	3464 KiB
			90	Accepted	57ms	3508 KiB
			91	Accepted	26ms	3380 KiB
			92	Accepted	20ms	3424 KiB
			93	Accepted	28ms	3492 KiB
			94	Accepted	323ms	5636 KiB
			95	Accepted	32ms	3816 KiB
			96	Accepted	135ms	6196 KiB
			97	Accepted	61ms	5056 KiB
			98	Accepted	123ms	6152 KiB
			99	Accepted	32ms	5632 KiB
			100	Accepted	17ms	3124 KiB
			101	Accepted	16ms	3124 KiB
			102	Accepted	17ms	3320 KiB
			103	Accepted	17ms	3192 KiB
			104	Accepted	16ms	3008 KiB
			105	Accepted	17ms	3220 KiB
			106	Accepted	16ms	3076 KiB
			107	Accepted	17ms	3000 KiB
			108	Accepted	16ms	3136 KiB
			109	Accepted	17ms	3016 KiB
			110	Accepted	16ms	3212 KiB
			111	Accepted	17ms	3320 KiB
			112	Accepted	17ms	3140 KiB
			113	Accepted	17ms	3104 KiB
			114	Accepted	18ms	3124 KiB
			115	Accepted	16ms	3112 KiB
			116	Accepted	17ms	3224 KiB
			117	Accepted	16ms	3204 KiB
			118	Accepted	17ms	3124 KiB
			119	Accepted	17ms	3124 KiB
			120	Accepted	17ms	3136 KiB
			121	Accepted	17ms	3124 KiB
			122	Accepted	16ms	3128 KiB
			123	Accepted	17ms	3208 KiB
			124	Accepted	16ms	3220 KiB
			125	Accepted	17ms	3228 KiB
			126	Accepted	16ms	3024 KiB
			127	Accepted	16ms	3356 KiB
			128	Accepted	16ms	3128 KiB
			129	Accepted	16ms	3136 KiB
130	Accepted		16ms	3120 KiB
131	Accepted		16ms	3020 KiB
132	Accepted		71ms	3312 KiB
133	Accepted		17ms	3380 KiB
134	Accepted		48ms	3380 KiB
135	Accepted		24ms	3352 KiB
136	Accepted		32ms	3380 KiB
137	Accepted		24ms	3124 KiB
138	Accepted		57ms	3296 KiB
139	Accepted		19ms	3380 KiB
140	Accepted		35ms	4312 KiB
141	Accepted		26ms	3708 KiB
142	Accepted		50ms	5288 KiB
143	Accepted		79ms	5496 KiB
144	Accepted		59ms	5920 KiB
145	Accepted		54ms	5136 KiB
146	Accepted		108ms	8084 KiB
147	Accepted		750ms	7292 KiB
148	Time limit exceeded		1.1s	5988 KiB
149	Time limit exceeded		1.1s	4440 KiB