Submission #1603454

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main(){
    int N, M;
    cin >> N >> M;
    vector<vector<int>> d(N, vector<int>(N, 1 << 29));
    for(int i=0; i<M; i++){
        int a, b, t;
        cin >> a >> b >> t;
        a--; b--;
        d[a][b] = t;
        d[b][a] = t;
    }
    for(int i=0; i<N; i++)
        d[i][i] = 0;
    for(int k=0; k<N; k++)
        for(int i=0; i<N; i++)
            for(int j=0; j<N; j++)
                d[i][j] = min(d[i][j], d[i][k]+d[k][j]);

    int ans = 1 << 30;
    for(int i=0; i<N; i++){
        int tmp = 0;
        for(int j=0; j<N; j++)
            tmp = max(tmp, d[i][j]);
        ans = min(ans, tmp);
    }
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result