Submission #1868756

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

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

#define INF 1e9

int main(void)
{
    int n, m, a, b, t;
    vector<vector<int>> v;

    cin >> n >> m;

    v.resize(n);

    rep(i, n){
        v[i].resize(n);
        rep(j, n){
            v[i][j] = INF;
            if(i == j){
                v[i][j] = 0;
            }
        }
    }

    rep(i, m){
        cin >> a >> b >> t;
        v[a - 1][b - 1] = t;
        v[b - 1][a - 1] = t;
    }

    rep(k, n){
        rep(i, n){
            rep(j, n){
                v[i][j] = min(v[i][j], v[i][k] + v[k][j]);
            }
        }
    }

    int ans = INF;
    rep(i, n){
        ans = min(ans, *max_element(v[i].begin(), v[i].end()));
    }

    cout << ans << endl;
}

Submission Info

Judge Result