Submission #2547073

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#ifdef LOCAL
    #define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#else
    #define debug(x) 0
#endif

// pair
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {return s << "(" << p.first << ", " << p.second << ")";}

// vector
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
	int len = v.size();
	for (int i = 0; i < len; ++i) {
		s << v[i]; if (i < len - 1) s << "\t";
	}
	return s;
}

// 2 dimentional vector
template<typename T> ostream& operator<<(ostream& s, const vector< vector<T> >& vv) {
	int len = vv.size();
	for (int i = 0; i < len; ++i) {
		s << vv[i] << endl;
	}
	return s;
}

// int acc = whole(accumulate, xs, 0ll);
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)

#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)

#define SZ(x) ((int)(x).size())

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)

#define perm(c) sort(all(c));for(bool c##p=1;c##p;c##p=next_permutation(all(c)))

#define pb push_back
#define mp make_pair

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

int gcd(int a,int b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

#define bit(n) (1LL<<(n))

const int INF = 1<<29;

int main() {
    cin.tie(0);
   	ios::sync_with_stdio(false);

    int n, m; cin >> n >> m;
    vector<vector<int> > d(n, vector<int>(n));
    rep(i, n) {
        rep(j, n) {
            if (i == j) {
                d[i][j] = 0;
            } else {
                d[i][j] = INF;
            }
        }
    }
    rep(i, m) {
        int u, v, c;
        cin >> u >> v >> c;
        u--; v--;
        d[u][v] = c; d[v][u] = c;
    }

    rep(k, n) {
        rep(i, n) {
            rep(j, n) {
                chmin(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }

    debug(d);

    int ans = INF;
    rep(i, n) {
        int maxd = 0;
        rep(j, n) {
            chmax(maxd, d[i][j]);
        }
        debug(maxd);
        chmin(ans, maxd);
    }

    cout << ans << endl;

    return 0;
}

Submission Info

Judge Result