ABC012 D - バスと避けられない運命

D - バスと避けられない運命

問題概要

N頂点M辺の連結な重み付き無向グラフが与えられます。各頂点との距離の最大値が最小となる頂点を選びその頂点との距離の最大値を出力してください。

制約

• 2 ≦ N ≦ 300
• N-1 ≦ M ≦ 44850
• 1 ≦ t_i ≦ 10³
• 二重辺、自己ループは存在しない

方針

任意の2頂点間の距離を求めたいのでワーシャル・フロイドを使います。制約から O(N³) が使えることを確認しておきます。あとは各頂点から他の頂点への距離の最大値をとっていってその中の最小値を出力すれば答えです。

Code

#include <bits/stdc++.h>
using namespace std;
const int IINF = INT_MAX;
#define REP(i, n) for (int i = 0; i < n; i++)

int main() {
    int n, m, d[305][305];
    cin >> n >> m;
    REP(i,n) fill(d[i], d[i]+n, IINF/2);
    REP(i,m){
        int a, b, t;
        cin >> a >> b >> t;
        a--;
        b--;
        d[a][b] = t;
        d[b][a] = t;
    }
    REP(k,n)REP(i,n)REP(j,n) d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
    int ans = IINF;
    REP(i,n){
        int tmp = 0;
        REP(j,n){
            if(i==j)continue;
            tmp = max(tmp, d[i][j]);
        }
        ans = min(ans, tmp);
    }
    cout << ans << endl;
    return 0;
}