Submission #2547078

---

Source Code Expand

#include <bits/stdc++.h>

#define rep(n) for(int i=0;i<n;i++)
#define repp(j, n) for(int j=0;j<n;j++)
#define reppp(i, m, n) for(int i=m;i<n;i++)
#define all(c) c.begin(), c.end()
#define rall(c) c.rbegin(), c.rend()
#define debug(x) cerr << #x << ": " << x << endl

using namespace std;

typedef long long ll;
typedef pair<ll, ll> Pll;
typedef pair<int, int> Pii;
struct edge{int from, to; ll cost;};

const ll MOD = 1000000007;
const long double EPS = 1e-10;

int main(){
    std::ios::sync_with_stdio(0); cin.tie(0);
    int n,m;
    cin >> n >> m;
    ll cost[n][n];
    fill(cost[0], cost[n], 1000000LL);
    rep(n) cost[i][i] = 0LL;
    int a,b,t;
    rep(m){
        cin >> a >> b >> t;
        a--; b--;
        cost[a][b] = t; cost[b][a] = t;
    }

    repp(k, n) repp(i, n) repp(j, n) cost[i][j] = min(cost[i][j], cost[i][k]+cost[k][j]);

    vector<ll> worst_cost(n, 0LL);
    rep(n) repp(j, i){
        worst_cost[i] = max(worst_cost[i], cost[i][j]);
        worst_cost[j] = max(worst_cost[j], cost[i][j]);
    }
    cout << *min_element(all(worst_cost)) << endl;
    return 0;
}

Submission Info

Judge Result