提出 #73341954

---

ソースコード 拡げる

// #pragma GCC target("avx2")
#pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
// #include<sys/time.h>
// #include<atcoder/segtree>
// #include<atcoder/modint>

using namespace std;

// using mint = atcoder::modint998244353;

using P = pair<int, int>;
const int M = 998244353;
const long long LM = 1LL << 60;


int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    int n, m;
    cin >> n >> m;
    vector<vector<P>> edge(n);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        --u;
        --v;
        edge[u].emplace_back(w, v);
        edge[v].emplace_back(w, u);
    }
    vector<vector<int>> dist(2, vector<int>(n, 1 << 30));
    priority_queue<pair<int, P>, vector<pair<int, P>>, greater<pair<int, P>>> pq;
    dist[0][0] = 1;
    pq.push({ dist[0][0], { 0, 0 } });

    auto f = [](int x, int w) {
        if ((x | w) == w) {
            return x;
        }
        for (int i = 0; i < 30; ++i) {
            if (((x >> i) & 1) == 0) {
                auto y = (x | (1 << i)) & ~((1 << i) - 1);
                if ((y | w) == w) {
                    return y;
                }
            }
        }
        return 1 << 30;
    };


    while (!pq.empty()) {
        auto p = pq.top();
        pq.pop();
        if (dist[p.second.first][p.second.second] != p.first) {
            continue;
        }
        for (auto&& e : edge[p.second.second]) {
            auto nj = e.second;
            auto ni = p.second.first || e.second == n - 1;
            auto nv = f(p.first, e.first);
            if (dist[ni][nj] > nv) {
                dist[ni][nj] = nv;
                pq.push({ dist[ni][nj], { ni, nj } });
            }
        }
    }
    int mi = dist[1][n - 1];
    int ma = mi;
    if (mi == (1 << 30)) {
        cout << "-1 -1\n";
        return 0;
    }

    for (int i = 0; i < n - 1; ++i) {
        for (auto&& e : edge[i]) {
            if (e.second == n - 1) {
                if (dist[0][i] <= e.first) {
                    ma = max(ma, e.first);
                }
            }
        }
    }
    cout << mi << ' ' << ma << '\n';

    return 0;
}

提出情報

ジャッジ結果