Submission #1759013

---

Source Code Expand

#include<functional>
#include<queue>
#include<vector>

struct Graph{
    Graph(int n) :E(n), d(n) {}
    using P = std::pair<int, int>;
    std::vector<std::vector<P>>E;
    std::vector<int>d;
    void addEdge(int a, int b, int c) { E[a].emplace_back(b, c); }
    void dijkstra(int s) {
        std::priority_queue<P, std::vector<P>, std::greater<>>Q;
        fill(d.begin(), d.end(), 1 << 30);
        Q.push({ d[s] = 0,s });
        while (!Q.empty()) {
            P e = Q.top(); Q.pop();
            if (e.first > d[e.second]) continue;
            for (P& a : E[e.second]) {
                int x = a.first, y = a.second + e.first;
                if (y < d[x]) d[x] = y, Q.push({ y,x });
            }
        }
    }
    int getCost(int n) { return d[n]; }
};

#include<algorithm>
#include<iostream>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    Graph G(n);
    for (int i = 0; i < m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        G.addEdge(--a, --b, c), G.addEdge(b, a, c);
    }
    int x = 1 << 30;
    for (int i = 0; i < n; ++i) {
        G.dijkstra(i);
        x = min(x, *max_element(G.d.begin(), G.d.end()));
    }
    cout << x << endl;
}

Submission Info

Judge Result