Submission #6858958

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 Weight = int;
using Flow = int;
struct Edge {
    int src, dst;
    Weight weight;
    Flow cap;
    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); }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>

using Weight = int;
using Flow = int;
struct Edge {
    int src, dst;
    Weight weight;
    Flow cap;
    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); }

// end template


Graph makeReversed(const Graph &g) {
    int n = g.size();
    Graph revg(n);
    for (auto &es : g) {
        for (auto &e: es) {
            Edge re = e;
            std::swap(re.src, re.dst);
            revg[re.src].push_back(re);
        }
    }
    return revg;
}

Weight bidirectionalDijkstra(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();
    using State = std::pair<Weight, int>;

    std::vector<Weight> dist[2];
    dist[0] = dist[1] = std::vector<Weight>(n, INF);
    dist[0][s] = dist[1][t] = 0;

    const Graph revg = makeReversed(g);
    const Graph* gs[2] = { &g, &revg };

    std::priority_queue<State, std::vector<State>, std::greater<State>> pq[2];
    pq[0].emplace(0, s);
    pq[1].emplace(0, t);

    Weight mu = INF;
    while (pq[0].size() && pq[1].size()) {
        if (pq[0].top().first + pq[1].top().first >= mu) break;
        int k = pq[0].top().first <= pq[1].top().first ? 0 : 1;
        Weight d;
        int v;
        std::tie(d, v) = pq[k].top();
        pq[k].pop();
        if (d < dist[k][v]) continue;
        for (auto &e : (*gs[k])[v]) {
            Weight w = e.dst;
            if (dist[k][w] > dist[k][v] + e.weight) {
                dist[k][w] = dist[k][v] + e.weight;
                pq[k].emplace(dist[k][w], w);
                mu = std::min(mu, dist[k][v] + e.weight + dist[1 - k][w]);
            }
        }
    }
    return mu;
}

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)

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, bidirectionalDijkstra(g, i, j));
            if(cand > res) break;
        }
        res = min(res, cand);
    }
    cout << res << endl;
}

Submission Info

Judge Result