Submission #66780072

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 P = pair<int,int>;
int main(){
    int N, M;
    cin >> N >> M;
    vector<vector<P>> G(N);
    for(int i = 0; i < M; i++){ 
        int A, B, W;
        cin >> A >> B >> W;
        A--; B--;
        G[A].push_back({B,W});
    }
    vector<int> dist(N, -1);
    queue<int> Q;
    dist[0] = 0; Q.push(0);
    while(!Q.empty()){
        int u = Q.front();
        Q.pop();
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
using namespace std;
using P = pair<int,int>;

int main(){
    int N, M;
    cin >> N >> M;
    vector<vector<P>> G(N);
    for(int i = 0; i < M; i++){ 
        int A, B, W;
        cin >> A >> B >> W;
        A--; B--;
        G[A].push_back({B,W});
    }

    vector<int> dist(N, -1);
    queue<int> Q;
    dist[0] = 0; Q.push(0);
    while(!Q.empty()){
        int u = Q.front();
        Q.pop();
        for(auto [v, w] : G[u]){
            if(dist[v] == -1){
                dist[v] = dist[u] ^ w;
                Q.push(v);
            }
        }
    }

    vector<int> basis;
    for(int u = 0; u < N; u++){
        for(auto [v, w] : G[u]){
            if(dist[u] != -1 && dist[v] != -1){
                int c = dist[u] ^ w ^ dist[v];
                for(int b : basis) c = min(c, c ^ b);
                if(c) basis.push_back(c);
            }
        }
    }
    
    sort(basis.begin(), basis.end(), greater<int>());

    if(dist[N - 1] == -1){
        cout << -1 << endl;
    }
    else {
        int ans = dist[N - 1];
        for(int b : basis){
            ans = min(ans, ans ^ b);
        }
        cout << ans << endl;
    }
}

Submission Info

Judge Result