Submission #66746965

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>
using namespace std;
int N, M;
vector<vector<pair<int, int>>> G;
vector<bool> used;
vector<int> dist;
vector<int> cycles;
void dfs(int u) {
    used[u] = true;
    for (auto [v, w] : G[u]) {
        if (!used[v]) {
            dist[v] = dist[u] ^ w;
            dfs(v);
        } else {
            // cycle
            int x = dist[u] ^ w ^ dist[v];
            for (int c : cycles) x = min(x, x ^ c);
            if (x > 0) cycles.push_back(x);
        }
    }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <iostream>
#include <vector>
using namespace std;
int N, M;
vector<vector<pair<int, int>>> G;
vector<bool> used;
vector<int> dist;
vector<int> cycles;
void dfs(int u) {
    used[u] = true;
    for (auto [v, w] : G[u]) {
        if (!used[v]) {
            dist[v] = dist[u] ^ w;
            dfs(v);
        } else {
            // cycle
            int x = dist[u] ^ w ^ dist[v];
            for (int c : cycles) x = min(x, x ^ c);
            if (x > 0) cycles.push_back(x);
        }
    }
}
int main() {
    cin >> N >> M;
    G.resize(N);
    used.resize(N);
    dist.resize(N);
    for (int i = 0; i < M; i++) {
        int u, v;
        int w;
        cin >> u >> v >> w;
        u--, v--;
        G[u].push_back({v, w});
    }
    dfs(0);
    if (!used[N - 1]) {
        cout << -1 << endl;
        return 0;
    }
    int ans = dist[N - 1];
    for (int c : cycles) ans = min(ans, ans ^ c);
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result