(cache)Submission #66748567 - AtCoder Beginner Contest 410

Contest Duration: 2025-06-14(Sat) 21:00 - 2025-06-14(Sat) 22:40 (local time) (100 minutes) Back to Home

Submission #66748567

Source Code Expand

Copy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from collections import deque
N,M = map(int,input().split())
graph = {i: [] for i in range(N)}
for i in range(M):
    u,v,w = map(int,input().split())
    graph[u-1].append((v-1, w))
queue = deque([(0, 0, 0)])
minimum = 999999
while queue:
    node,cost,depth = queue.popleft()
    if node == N-1:
        minimum = min(minimum, cost)
    if depth == M * 2:
        continue
    for next_node, next_cost in graph[node]:
        if next_node != node:
            queue.append((next_node, cost ^ next_cost, depth + 1))
print(minimum if minimum != 999999 else -1)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

from collections import deque

N,M = map(int,input().split())
graph = {i: [] for i in range(N)}
for i in range(M):
    u,v,w = map(int,input().split())
    graph[u-1].append((v-1, w))

queue = deque([(0, 0, 0)])
minimum = 999999
while queue:
    node,cost,depth = queue.popleft()
    if node == N-1:
        minimum = min(minimum, cost)
    if depth == M * 2:
        continue
    for next_node, next_cost in graph[node]:
        if next_node != node:
            queue.append((next_node, cost ^ next_cost, depth + 1))
print(minimum if minimum != 999999 else -1)

Submission Info

Submission Time	2025-06-14 21:34:11
Task	D - XOR Shortest Walk
User	kangping
Language	Python (PyPy 3.10-v7.3.12)
Score	0
Code Size	581 Byte
Status	TLE
Exec Time	2276 ms
Memory	1330004 KiB

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

0 / 400

Status

× 3

AC	× 27
TLE	× 6

Set Name	Test Cases
Sample	sample_01.txt, sample_02.txt, sample_03.txt
All	hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, hand_06.txt, hand_07.txt, hand_08.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, sample_01.txt, sample_02.txt, sample_03.txt

Case Name	Status	Exec Time	Memory
hand_01.txt	AC	64 ms	76808 KiB
hand_02.txt	AC	65 ms	77072 KiB
hand_03.txt	AC	66 ms	76704 KiB
hand_04.txt	AC	65 ms	76912 KiB
hand_05.txt	AC	64 ms	77064 KiB
hand_06.txt	AC	64 ms	76732 KiB
hand_07.txt	AC	64 ms	76752 KiB
hand_08.txt	AC	64 ms	76968 KiB
random_01.txt	AC	65 ms	77004 KiB
random_02.txt	AC	70 ms	76704 KiB
random_03.txt	AC	65 ms	76964 KiB
random_04.txt	AC	68 ms	76968 KiB
random_05.txt	AC	65 ms	76828 KiB
random_06.txt	AC	66 ms	76840 KiB
random_07.txt	AC	65 ms	76620 KiB
random_08.txt	AC	70 ms	77024 KiB
random_09.txt	AC	65 ms	76616 KiB
random_10.txt	AC	74 ms	81092 KiB
random_11.txt	AC	65 ms	76700 KiB
random_12.txt	AC	70 ms	76772 KiB
random_13.txt	TLE	2276 ms	1325192 KiB
random_14.txt	TLE	2263 ms	1083988 KiB
random_15.txt	TLE	2276 ms	1330004 KiB
random_16.txt	AC	66 ms	76712 KiB
random_17.txt	AC	76 ms	80584 KiB
random_18.txt	AC	78 ms	80956 KiB
random_19.txt	AC	139 ms	101928 KiB
random_20.txt	TLE	2261 ms	1045680 KiB
random_21.txt	TLE	2264 ms	1095164 KiB
random_22.txt	TLE	2264 ms	1111196 KiB
sample_01.txt	AC	65 ms	76600 KiB
sample_02.txt	AC	64 ms	76944 KiB
sample_03.txt	AC	64 ms	76800 KiB