Submission #1777118

---

Source Code Expand

#include <iostream>
#include <vector>
#include <cstdlib>

using namespace std;
int min(int a, int b){
	if (a < b)
		return a;
	else
		return b;
}

int max(int a, int b){
	return a + b - min(a, b);
}


int main(void){
	int n, m;

	cin >> n >> m;

	vector< vector<int> > d(n, vector<int>(n, 50000*300));

	int a, b, c;

	for (int i = 0; i < m; i++){
		cin >> a >> b >> c;
		d[a-1][b-1] = c;
		d[b-1][a-1] = c;
	}

	for (int i = 0; i < n; i++){
		d[i][i] = 0;
	}

	for (int k = 0; k < n; k++){
		for (int i = 0; i < n; i++){
			for (int j = 0; j < n; j++){
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
			}
		}
	}

	int max1 = 50000*300, max2;
	for (int k = 0; k < n; k++){
		max2 = 0;
		for (int i = 0; i < n; i++){
			max2 = max(d[k][i], max2);
		}
		max1 = min(max1, max2);
	}



	cout << max1 << endl;

	return 0;
}

Submission Info

Judge Result