Submission #4019859

---

Source Code Expand

#include<iostream>
using namespace std;

const int MAX_N = 303;
const int INF = 1 << 30;

int graph[MAX_N][MAX_N];

int main() {
    int N, M, a, b, t;
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (i == j) continue;
            else {
                graph[i][j] = INF;
            }
        }
    }
    for (int i = 0; i < M; i++) {
        cin >> a >> b >> t;
        a--, b--;
        graph[a][b] = graph[b][a] = t;
    }
    for (int k = 0; k < N; k++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (graph[i][k] == INF || graph[k][j] == INF) continue;
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[j][k]);
            }
        }
    }
    int ans = INF;
    for (int i = 0; i < N; i++) {
        int max_time = 0;
        for (int j = 0; j < N; j++) max_time = max(max_time, graph[i][j]);
        ans = min(ans, max_time);
    }
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result