Submission #63557189

Source Code Expand

N, M = map(int, input().split())
G = [[] for _ in range(N)]

for _ in range(M):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    G[u].append((v, w))
    G[v].append((u, w))
# print(G)
INF = float('inf')

dp = [INF] * N
visited = [False] * N
dp[0] = 0
visited[0] = True
ans = INF


def dfs(now, lst=-1):
    global ans
    if now == lst:
        return
    for to, w in G[now]:
        if visited[to]:
            continue
        if to == N - 1:
            ans = min(ans, dp[now] ^ w)
        visited[to] = True
        dp[to] = dp[now] ^ w
        dfs(to, now)
        visited[to] = False
        dp[to] = dp[now] ^ w

dfs(0)
# print(dp)
print(ans)

Submission Info

Submission Time
Task D - Minimum XOR Path
User hirohito1971
Language Python (PyPy 3.10-v7.3.12)
Score 400
Code Size 703 Byte
Status AC
Exec Time 174 ms
Memory 82728 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 3
AC × 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 55 ms 76804 KiB
00_sample_01.txt AC 58 ms 76544 KiB
00_sample_02.txt AC 63 ms 76516 KiB
01_test_00.txt AC 59 ms 76388 KiB
01_test_01.txt AC 57 ms 76576 KiB
01_test_02.txt AC 57 ms 76548 KiB
01_test_03.txt AC 61 ms 76764 KiB
01_test_04.txt AC 61 ms 76652 KiB
01_test_05.txt AC 61 ms 76428 KiB
01_test_06.txt AC 64 ms 76516 KiB
01_test_07.txt AC 65 ms 76376 KiB
01_test_08.txt AC 59 ms 80228 KiB
01_test_09.txt AC 73 ms 82568 KiB
01_test_10.txt AC 61 ms 76356 KiB
01_test_11.txt AC 65 ms 81256 KiB
01_test_12.txt AC 63 ms 76528 KiB
01_test_13.txt AC 70 ms 81424 KiB
01_test_14.txt AC 69 ms 81416 KiB
01_test_15.txt AC 86 ms 82728 KiB
01_test_16.txt AC 58 ms 76464 KiB
01_test_17.txt AC 102 ms 82292 KiB
01_test_18.txt AC 59 ms 76628 KiB
01_test_19.txt AC 170 ms 82128 KiB
01_test_20.txt AC 154 ms 82072 KiB
01_test_21.txt AC 174 ms 82116 KiB
01_test_22.txt AC 168 ms 82432 KiB
01_test_23.txt AC 173 ms 82160 KiB
01_test_24.txt AC 60 ms 76708 KiB
01_test_25.txt AC 61 ms 76844 KiB
01_test_26.txt AC 56 ms 76364 KiB
01_test_27.txt AC 58 ms 76304 KiB
01_test_28.txt AC 55 ms 76564 KiB