Submission #1098600

---

Source Code Expand

#include <bits/stdc++.h>
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(c) begin(c), end(c)
#define dump(x) cerr << __LINE__ << ":\t" #x " = " << (x) << endl

using Weight = int;
using Capacity = int;
struct Edge {
    int src, dst;
    Weight weight;
    Edge() : src(0), dst(0), weight(0) {}
    Edge(int s, int d, Weight w) : src(s), dst(d), weight(w) {}
};
using Edges = std::vector<Edge>;
using Graph = std::vector<Edges>;
using Array = std::vector<Weight>;
using Matrix = std::vector<Array>;

void add_edge(Graph &g, int a, int b, Weight w = 1) {
    g[a].emplace_back(a, b, w);
    g[b].emplace_back(b, a, w);
}
void add_arc(Graph &g, int a, int b, Weight w = 1) {
    g[a].emplace_back(a, b, w);
}

Weight bidirectional_dijkstra(const Graph &g, int s, int t){
    if(s == t) return 0;
    constexpr Weight INF = std::numeric_limits<Weight>::max() / 2;
    int n = g.size();
    std::vector<Weight> dist[2];
    dist[0] = dist[1] = std::vector<Weight>(n, INF);
    dist[0][s] = dist[1][t] = 0;
    using state = std::pair<Weight, int>;
    std::priority_queue<state, std::vector<state>, std::greater<state>> q[2];
    q[0].emplace(0, s);
    q[1].emplace(0, t);
    Weight mu = INF;
    while (q[0].size() && q[1].size()) {
        if (q[0].top().first + q[1].top().first >= mu) break;
        int k = q[0].top().first <= q[1].top().first ? 0 : 1;
        Weight d;
        int v;
        std::tie(d, v) = q[k].top();
        q[k].pop();
        if (d < dist[k][v]) continue;
        for (auto &e: g[v]) {
            int w = e.dst;
            if (dist[k][w] > dist[k][v] + e.weight) {
                dist[k][w] = dist[k][v] + e.weight;
                q[k].emplace(dist[k][w], w);
                mu = std::min(mu, dist[k][v] + e.weight + dist[1 - k][w]);
            }
        }
    }
    return mu;
}

using namespace std;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    int n, m;
    cin >> n >> m;
    Graph g(n);
    rep(i, m){
        int a, b, t;
        cin >> a >> b >> t;
        --a; --b;
        add_edge(g, a, b, t);
    }
    int res = 1e9;
    rep(i, n){
        int cand = 0;
        rep(j, n){
            cand = max(cand, bidirectional_dijkstra(g, i, j));
            if(cand > res) break;
        }
        res = min(res, cand);
    }
    cout << res << endl;
}

Submission Info

Judge Result