Submission #2250933

---

Source Code Expand

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define ALL(A) A.begin(), A.end()
#define INF 1<<28

using namespace std;

typedef long long ll;
typedef pair<int, int> P;

const int MAX_N = 303;

int dist[MAX_N][MAX_N];


int main()
{
	memset(dist, 0, sizeof(dist));
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int N, M; cin >> N >> M;
	rep (i, N) rep (j, N) dist[i][j] = INF;

	rep (i, M){
		int a, b, t; cin >> a >> b >> t;
		--a, --b;
		dist[a][b] = t;
		dist[b][a] = t;
	} // end rep

	for (int k = 0; k < N; ++k){
		for (int i = 0; i < N; ++i){
			for (int j = 0;j < N; ++j){
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
			} // end for
		} // end for
	} // end for

	int res = INF;
	for (int i = 0; i < N; ++i){
		int curr = 0;
		for (int j = 0; j < N; ++j){
			if (i == j) continue;
			curr = max(curr, dist[i][j]);
		} // end for
		res = min(res, curr);
	} // end for
	
	cout << res << endl;
	
	return 0;
}

Submission Info

Judge Result