(cache)Submission #63532257 - AtCoder Beginner Contest 396

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

Submission #63532257

Source Code Expand

Copy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from collections import deque
N,M = map(int,input().split())
graph = {i:[] for i in range(N)}
for _ in range(M):
    u,v,w = map(int,input().split())
    graph[u-1].append((v-1,w))
    graph[v-1].append((u-1,w))
queue = deque([])
for i in range(len(graph[0])):
    queue.append((graph[0][i][0],graph[0][i][1],set([0,graph[0][i][0]])))
min_w = float('inf')
while queue:
    v,w,visited = queue.popleft()
    if v == N-1:
        min_w = min(min_w,w)
        continue
    for i in range(len(graph[v])):
        if graph[v][i][0] not in visited:
            visited_copy = visited.copy()
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

from collections import deque

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

queue = deque([])
for i in range(len(graph[0])):
    queue.append((graph[0][i][0],graph[0][i][1],set([0,graph[0][i][0]])))
min_w = float('inf')
while queue:
    v,w,visited = queue.popleft()
    if v == N-1:
        min_w = min(min_w,w)
        continue
    for i in range(len(graph[v])):
        if graph[v][i][0] not in visited:
            visited_copy = visited.copy()
            visited_copy.add(graph[v][i][0])
            queue.append((graph[v][i][0],w^graph[v][i][1],visited_copy))
print(min_w)

Submission Info

Submission Time	2025-03-08 21:38:13
Task	D - Minimum XOR Path
User	kangping
Language	Python (CPython 3.11.4)
Score	400
Code Size	740 Byte
Status	AC
Exec Time	337 ms
Memory	77112 KiB

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

400 / 400

Status

× 3

× 32

Set Name	Test Cases
Sample	00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All	00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_test_00.txt, 01_test_01.txt, 01_test_02.txt, 01_test_03.txt, 01_test_04.txt, 01_test_05.txt, 01_test_06.txt, 01_test_07.txt, 01_test_08.txt, 01_test_09.txt, 01_test_10.txt, 01_test_11.txt, 01_test_12.txt, 01_test_13.txt, 01_test_14.txt, 01_test_15.txt, 01_test_16.txt, 01_test_17.txt, 01_test_18.txt, 01_test_19.txt, 01_test_20.txt, 01_test_21.txt, 01_test_22.txt, 01_test_23.txt, 01_test_24.txt, 01_test_25.txt, 01_test_26.txt, 01_test_27.txt, 01_test_28.txt

Case Name	Status	Exec Time	Memory
00_sample_00.txt	AC	11 ms	9320 KiB
00_sample_01.txt	AC	11 ms	9296 KiB
00_sample_02.txt	AC	11 ms	9324 KiB
01_test_00.txt	AC	11 ms	9328 KiB
01_test_01.txt	AC	11 ms	9252 KiB
01_test_02.txt	AC	11 ms	9244 KiB
01_test_03.txt	AC	11 ms	9276 KiB
01_test_04.txt	AC	11 ms	9332 KiB
01_test_05.txt	AC	11 ms	9356 KiB
01_test_06.txt	AC	11 ms	9328 KiB
01_test_07.txt	AC	12 ms	9288 KiB
01_test_08.txt	AC	11 ms	9376 KiB
01_test_09.txt	AC	18 ms	10316 KiB
01_test_10.txt	AC	11 ms	9264 KiB
01_test_11.txt	AC	17 ms	10212 KiB
01_test_12.txt	AC	11 ms	9348 KiB
01_test_13.txt	AC	13 ms	9552 KiB
01_test_14.txt	AC	17 ms	9984 KiB
01_test_15.txt	AC	42 ms	15248 KiB
01_test_16.txt	AC	11 ms	9316 KiB
01_test_17.txt	AC	166 ms	40312 KiB
01_test_18.txt	AC	11 ms	9340 KiB
01_test_19.txt	AC	334 ms	77036 KiB
01_test_20.txt	AC	334 ms	77088 KiB
01_test_21.txt	AC	337 ms	77112 KiB
01_test_22.txt	AC	333 ms	77036 KiB
01_test_23.txt	AC	334 ms	76892 KiB
01_test_24.txt	AC	11 ms	9328 KiB
01_test_25.txt	AC	11 ms	9264 KiB
01_test_26.txt	AC	11 ms	9308 KiB
01_test_27.txt	AC	11 ms	9256 KiB
01_test_28.txt	AC	11 ms	9260 KiB