1090. Highways

#include "iostream"
#include "memory.h"
#include "cstdio"
using namespace std;

int grap[500][500];
int ans;
int dis[500];
bool visited[500];

void prime(int n){
	int source = 1;
	for (int i = 1; i <= n; i++){
		dis[i] = grap[source][i];
		visited[i] = false;
	}
	visited[source] = true;
	for (int j = 1; j < n; j++){
		int min =65535;
		int index = 0;
		for (int i = 1; i <= n; i++){
			if (!visited[i] && dis[i] < min){
				min = dis[i];
				index = i;
			}
		}
		visited[index] = true;
		if (ans < min)
			ans = min;
		for (int i = 1; i <= n; i++){
			if(!visited[i] && (grap[index][i]) < dis[i]){
				dis[i] = grap[index][i];
			}
		}
	}
}

int main(){
	int n;
	bool ok = false;
	int t;
	cin >> t;
	while ( t--){
		if (ok)
			cout << endl;
		ok = true;
		cin >> n;
		if (n < 3){
			cout << "\n";
			continue;
		}
		ans = -1000;
		for (int i = 1; i <= n; i++){
			for (int j = 1; j <= n; j++){
				cin >> grap[i][j];
				grap[j][i] = grap[i][j];
			}
		}
		prime(n);
		cout << ans << endl;
	}
}

1090. Highways

原文：http://blog.csdn.net/liujan511536/article/details/42682291