Submission #66750427

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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 1<<30;
struct Edge {
    int to, weight;
  };
int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<Edge>> graph(n + 1);
    vector<int> basis;
    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        graph[a].push_back({b, w});
      }
    vector<int> dist(n + 1, INF);
    queue<pair<int, int>> q;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 1<<30;

struct Edge {
    int to, weight;
  };

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<Edge>> graph(n + 1);
    vector<int> basis;
    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        graph[a].push_back({b, w});
      }
    vector<int> dist(n + 1, INF);
    queue<pair<int, int>> q;
    dist[1] = 0;
    q.push({1, 0});
    while (!q.empty()) {
        auto [v, d] = q.front(); q.pop();
        for (auto &e : graph[v]) {
            int to = e.to;
            int nd = d ^ e.weight;
            if (dist[to] > nd) {
                dist[to] = nd;
                q.push({to, nd});
              }
            else {
                int x = nd ^ dist[to];
                for (int b : basis) x = min(x, x ^ b);
                if (x > 0) basis.push_back(x);
              }
          }
      }
    int x = dist[n];
    if (x == INF) cout << -1 << endl;
    else {
        for (int b : basis) x = min(x, x ^ b);
        cout << x << endl;
      }
    return 0;
  }

Submission Info

Judge Result