题干：

The island nation of Flatopia is perfectly flat. Unfortunately, Flatopia has no public highways. So the traffic is difficult in Flatopia. The Flatopian government is aware of this problem. They're planning to build some highways so that it will be possible to drive between any pair of towns without leaving the highway system. 

Flatopian towns are numbered from 1 to N. Each highway connects exactly two towns. All highways follow straight lines. All highways can be used in both directions. Highways can freely cross each other, but a driver can only switch between highways at a town that is located at the end of both highways. 

The Flatopian government wants to minimize the length of the longest highway to be built. However, they want to guarantee that every town is highway-reachable from every other town.

Input

The first line of input is an integer T, which tells how many test cases followed. 
The first line of each case is an integer N (3 <= N <= 500), which is the number of villages. Then come N lines, the i-th of which contains N integers, and the j-th of these N integers is the distance (the distance should be an integer within [1, 65536]) between village i and village j. There is an empty line after each test case.

Output

For each test case, you should output a line contains an integer, which is the length of the longest road to be built such that all the villages are connected, and this value is minimum.

Sample Input

1

3
0 990 692
990 0 179
692 179 0

Sample Output

692

Hint

Huge input,scanf is recommended.

题目大意：

A国没有高速公路，因此A国的交通很困难。政府意识到了这个问题并且计划建造一些高速公路，以至于可以在不离开高速公路的情况下在任意两座城镇之间行驶。

A国的城镇编号为1到N, 每条高速公路连接这两个城镇，所有高速公路都可以在两个方向上使用。高速公路可以自由的相互交叉。

A国政府希望尽量减少最长高速公路的建设时间（使建设的最长的高速公路最短），但是他们要保证每个城镇都可以通过高速公路到达任意一座城镇。

解题报告：

   介于有的题目确实Prim算法效率极高（对于n=2000这样的完全图，用Kruskal就作死了），我决定顺道学习一下Prim、、、（

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 2e5 + 5;
const int INF = 0x3f3f3f3f;
int n;
int cost[666][666];
int dis[666];
bool vis[666];
int prim() {//这种写法适用于已知点是1~N的。
	int res = 0;
	for(int i = 0; i<=n; i++) dis[i] = INF, vis[i] = 0;
	dis[1] = 0;//假设从1开始
	while(1) {
		int v = 0;//这种写法的话上面初始化必须从0开始了。。
		for(int i = 1; i<=n; i++) {
			if(!vis[i] && dis[i] < dis[v]) v = i;
		}
		if(!v) break;//这种写法的话上面初始化必须从0开始了。。 
		vis[v] = 1;
		res = max(res,dis[v]) ;
		for(int i = 1; i<=n; i++) {
			if(!vis[i] && cost[v][i] < dis[i]) dis[i] = cost[v][i];//!vis[i]这一句加不加都一样的。
		}
	} 
	return res;
}
int main()
{
	int t;
	cin>>t;
	while(t--) {
		scanf("%d",&n);
		for(int i = 1; i<=n; i++) {
			for(int j = 1; j<=n; j++) {
				scanf("%d",&cost[i][j]);
			}	
		}
		int ans = prim();
		printf("%d\n",ans);
	}


	return 0 ;
 }

Prim的另一种写法：（相对常用一些）

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 2e5 + 5;
const int INF = 0x3f3f3f3f;
int n;
int cost[666][666];
int dis[666];
bool vis[666];
int prim() {//这种写法不一定必须点是1~N的，也可以是0~N-1的，只需要把下面第三行那个改成dis[0]=0就行了。
	int res = 0;
	for(int i = 1; i<=n; i++) dis[i] = INF, vis[i] = 0;//这种写法的话初始化就可以从1开始 
	dis[1] = 0;//假设从1开始
	while(1) {
		int v,minw = INF;
		for(int i = 1; i<=n; i++) {
			if(!vis[i] && dis[i] < minw) v = i,minw = dis[i];
		}
		if(minw == INF) break;
		vis[v] = 1;
		res = max(res,dis[v]) ;
		for(int i = 1; i<=n; i++) {
			if(!vis[i] && cost[v][i] < dis[i]) dis[i] = cost[v][i];
		}
	} 
	return res;
}
int main()
{
	int t;
	cin>>t;
	while(t--) {
		scanf("%d",&n);
		for(int i = 1; i<=n; i++) {
			for(int j = 1; j<=n; j++) {
				scanf("%d",&cost[i][j]);
			}	
		}
		int ans = prim();
		printf("%d\n",ans);
	}


	return 0 ;
 }