Submission #66745724

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
const int INF = 1e9;
struct Edge
{
   int to;
   int weight;
};
std::vector<std::vector<Edge>> adj;
std::vector<int> path_xor;
std::vector<bool> visited;
std::vector<int> cycle_basis;
void add_to_basis(int val)
{
   for (int b : cycle_basis)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

const int INF = 1e9;

struct Edge
{
   int to;
   int weight;
};

std::vector<std::vector<Edge>> adj;
std::vector<int> path_xor;
std::vector<bool> visited;
std::vector<int> cycle_basis;

void add_to_basis(int val)
{
   for (int b : cycle_basis)
   {
      val = std::min(val, val ^ b);
   }
   if (val > 0)
   {
      cycle_basis.push_back(val);
   }
}

void dfs_build_basis(int u, int current_xor_sum)
{
   visited[u] = true;
   path_xor[u] = current_xor_sum;

   for (const auto &edge : adj[u])
   {
      int v = edge.to;
      int w = edge.weight;

      if (!visited[v])
      {
         dfs_build_basis(v, current_xor_sum ^ w);
      }
      else
      {
         int cycle_xor_val = current_xor_sum ^ w ^ path_xor[v];
         add_to_basis(cycle_xor_val);
      }
   }
}

int main()
{
   int N, M;
   std::cin >> N >> M;

   adj.resize(N + 1);
   path_xor.assign(N + 1, INF); // INF で初期化
   visited.assign(N + 1, false);

   for (int i = 0; i < M; ++i)
   {
      int A, B, W;
      std::cin >> A >> B >> W;
      adj[A].push_back({B, W});
   }

   dfs_build_basis(1, 0);

   if (path_xor[N] == INF)
   {
      std::cout << -1 << std::endl;
      return 0;
   }

   int min_walk_xor = path_xor[N];

   for (int b : cycle_basis)
   {
      min_walk_xor = std::min(min_walk_xor, min_walk_xor ^ b);
   }

   std::cout << min_walk_xor << std::endl;

   return 0;
}

Submission Info

Judge Result