Submission #627867

---

Source Code Expand

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

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

const int INF = 10000000;
const int MAX_V = 300;
int d[MAX_V][MAX_V];
int E, V;

void init() {
    REP(i, V) {
        REP(j, V) {
            if (i == j) d[i][j] = 0;
            else        d[i][j] = INF;
        }
    }
}

void make() {
    REP(i, E) {
        int u, v, c;
        cin >> u >> v >> c;
        u--; v--;
        d[u][v] = c; d[v][u] = c;
    }
}

void wf() {
    REP(k, V) {
        REP(i, V) {
            REP(j, V) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
}

void answer() {
    int mi = INF;
    REP(i, V) {
        int ma = 0;
        REP(j, V) {
            ma = max(ma, d[i][j]);
        }
        mi = min(mi, ma);
    }

    cout << mi << endl;
}

void solve() {

    cin >> V >> E;

    init();

    make();

    wf();

    answer();
}

int main() {
    solve();
    return 0;
}

Submission Info

Judge Result