Submission #66760513

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;
using ll = long long;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define rep(i,a,b) for(int i=a;i<b;i++)
int main(){
    int n, m;
    cin >> n >> m;
    vector<set<pair<int, int>>> edge(n);
    int a, b, w;
    rep(i, 0, m){
        cin >> a >> b >> w;
        a--;b--;
        edge[a].insert({b, w});
    }
    vector<int> dist(n, -1);
    vector<int> basis;
    dist[0] = 0;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define rep(i,a,b) for(int i=a;i<b;i++)

int main(){
    int n, m;
    cin >> n >> m;
    vector<set<pair<int, int>>> edge(n);
    int a, b, w;
    rep(i, 0, m){
        cin >> a >> b >> w;
        a--;b--;
        edge[a].insert({b, w});
    }

    vector<int> dist(n, -1);
    vector<int> basis;
    dist[0] = 0;
    queue<int> q;
    q.push(0);

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto [v, w] : edge[u]) {
            int new_dist = dist[u] ^ w;
            if (dist[v] == -1) {
                dist[v] = new_dist;
                q.push(v);
            } else {
                // サイクル
                int cycle = dist[v] ^ new_dist;
                for (int b : basis){
                    cycle = min(cycle, cycle ^ b);
                }
                if (cycle != 0) basis.push_back(cycle);
            }
        }
    }

    int ans = dist[n - 1];
    if(ans != -1){
        for (int b : basis){
            ans = min(ans, ans ^ b);
        }
    }

    cout << ans << endl;
}

Submission Info

Judge Result