Submission #66318835

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;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M;
    cin >> N >> M;
    vector<vector<pair<int,int>>> adj(N + 1);
    for (int i = 0; i < M; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }
    int ban = 0;
    vector<char> visited(N + 1);
    for (int k = 29; k >= 0; k--) {
        int temp_ban = ban | (1 << k);
        fill(visited.begin(), visited.end(), 0);
        vector<int> stk;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M;
    cin >> N >> M;
    vector<vector<pair<int,int>>> adj(N + 1);
    for (int i = 0; i < M; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }
    int ban = 0;
    vector<char> visited(N + 1);
    for (int k = 29; k >= 0; k--) {
        int temp_ban = ban | (1 << k);
        fill(visited.begin(), visited.end(), 0);
        vector<int> stk;
        stk.reserve(N);
        visited[1] = 1;
        stk.push_back(1);
        while (!stk.empty()) {
            int v = stk.back();
            stk.pop_back();
            for (auto &p : adj[v]) {
                int u = p.first;
                int w = p.second;
                if (!visited[u] && ((w & temp_ban) == 0)) {
                    visited[u] = 1;
                    stk.push_back(u);
                }
            }
        }
        if (visited[N]) {
            ban = temp_ban;
        }
    }
    int ans = 0;
    for (int k = 0; k < 30; k++) {
        if ((ban & (1 << k)) == 0) {
            ans |= (1 << k);
        }
    }
    cout << ans << "\n";
    return 0;
}

Submission Info

Judge Result