Submission #63643149

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
"""
<方針>
- `N` が小さいので、計算量の問題ではなく、実装力が試されそう。
- パスを全列挙すれば良さそう。
"""
# ライブラリ
from collections import deque
# 入力
N, M = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
  u, v, w = map(int, input().split())
  u -= 1
  v -= 1
  E[u].append([v, w])
  E[v].append([u, w])
# 非再帰DFS
q = deque()
# 最初の頂点から始める。
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

"""
<方針>
- `N` が小さいので、計算量の問題ではなく、実装力が試されそう。
- パスを全列挙すれば良さそう。
"""
# ライブラリ
from collections import deque

# 入力
N, M = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
  u, v, w = map(int, input().split())
  u -= 1
  v -= 1
  E[u].append([v, w])
  E[v].append([u, w])

# 非再帰DFS
q = deque()
# 最初の頂点から始める。
q.append([0, 0, [False]*N])
# 答え
ans = float("inf")
while q:
  # 頂点, 総XOR, 訪れた頂点
  u, xor, visited = q.pop() # DFS
  
  # 自分を訪れた頂点に登録する。
  visited[u] = True
  
  # 終了状態になれば、答えを更新する。
  if (u == N - 1):
    ans = min(ans, xor)
  
  # 次のパスを見る
  for v, w in E[u]:
    # 訪れた頂点でなければ、
    if not visited[v]:
      # 次の頂点を追加する。
      q.append([v, xor^w, visited[:]])

# 出力
print(ans)

Submission Info

Judge Result