Submission #2245633

---

Source Code Expand

#include "bits/stdc++.h"
using namespace std;
#define FOR(i,a,b) for(int i =(a);i<(b);i++)
#define REP(i,n) for(int i=0;i<(n);i++)
#define REPm(i,n) for(int i=(n)-1;i>=0;i--)
#define REP1(i,n) for(int i=1;i<=(n);i++)
#define mp make_pair
#define inf 1e9
typedef long long ll;
int dis[300][300];
int main(){
    int N,M;
    cin >> N >> M;
    REP(i,N){
        REP(j,N){
            if(i == j) dis[i][j] = 0;
            else dis[i][j] = inf;
        }
    }
    REP(i,M){
        int a,b,t;
        cin >> a >> b >> t;
        dis[a-1][b-1] = t;
        dis[b-1][a-1] = t;
    }
    REP(k,N){
        REP(i,N){
            REP(j,N){
                if(dis[i][k] != inf && dis[k][j] != inf && dis[i][j] > dis[i][k] + dis[k][j]){
                    dis[i][j] = dis[i][k] + dis[k][j];
                }
            }
        }
    }
    int ans = inf;
    REP(i,N){
        int m = 0;
        REP(j,N){
            m = max(m,dis[i][j]);
        }
        ans = min(ans,m);
    }
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result