题目链接：http://poj.org/problem?id=2485
题意：一个地方F，没有Highways，交通不便，要建 Highways，每个Highway连接两个城镇，所有的Highways都是直线的。
样例输入意思：
T 案例数
N 城镇数
下面N行N列，以矩阵的形式
v1 v2 v3
v1 0 990 692
v2 990 0 179
v3 692 179 0
样例输出意思：
明显路径是 v1-v3-v2，路径中最大的数是692，输出的就是它
思路：
最小生成树问题，一般用prim，kuskal算法 。prim算法是以顶点来扩展的。把每次找到的顶点加入顶点集U，然后下次再找与U相邻且最小的顶点，加入U，依次，得到最小生成树。
参考：http://en.wikipedia.org/wiki/Prim's_algorithm
#include <stdio.h>
#include <string.h>
#define M 502
#define INF 99999
int prim[M][M];
int visit[M];
int Len[M]; //Len[i] 记录顶点集U到i的最短距离，注意区别dijkstra中的dis[i]
int n;
int ans;
int prim_solve(int xx)
{
int minx;
int i,j,k;
memset(visit,0,sizeof(visit)); //开始时都未访问
ans = -1;
for (i = 1; i <= n; i++)
{
Len[i] = prim[xx][i];
}
Len[xx] = 0;
visit[xx] = 1; //此时U中只有起点xx
for(i = 1; i< n; i++) // 注意：不能=,因为xx起点已经访问过，所以只需再访问n-1个
{
minx = INF;
for(j = 1; j <= n; j++ ) //很像dijkstra中的吧，但注意：这里的Len[i]与dijkstra中dis[i]意义相当不同
{ //这里找的是：与顶点集U相邻的距离最小值
if ( !visit[j] && Len[j] < minx)
{
minx = Len[j];
k = j;
}
}
visit[k] = 1; //找到，加入U
if (ans < minx) //保存最短路径中最大的一条边，比如样例中692
{
ans = minx;
}
//i=1时，U中只有起点xx和新加入的k，Len[j]与prim[j]比较：就是比较xx到j的距离和新加入U的k顶点到j的距离
//之后，Len[j]就是U到j的最短距离啦，这样把U中所有顶点看成一个，Len[j]就是U到j(V-U中任意一个)的最短距离
//以此类推，i>1 时，每次都把原来的顶点集U到j的距离和新加入的k到j的距离比较，这样得到了新U到j的最短距离
//从而,就得到了新U到V-U中任一顶点的距离，保存在 Len中
for (j = 1; j <= n; j++)
{
if ( !visit[j] && Len[j] > prim[k][j])
{
Len[j] = prim[k][j];
}
}
}
return ans;
}
int main()
{
int T;
int i,j;
scanf("%d",&T);
while(T--)
{
memset(prim,0,sizeof(prim));
scanf("%d",&n);
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j ++)
{
scanf("%d",&prim[i][j]);
}
printf("%d\n",prim_solve(1)); //以第一个顶点开始，也可以是其他，无所谓，改成2。。。。一样
}
return 0;
}
你会觉得prim代码实现是来很像dijkstra，参考http://blog.csdn.net/bill_ming/article/details/7578037
prim是计算最小生成树的算法，dijkstra是计算最短路径的算法。
他们都是从几何V-U中不断选出权值最小的顶点加入U，那他们是否可以互用吗？
必然不可以嘛！
他们的不同之处是：
prim是把U中的点看成一个整体，每次寻找V-U中和U距离最小的顶点加入U。而dijkstra是相对于源点V0而言的，每次寻找的是V-U中里V0最近的顶点。
所以：
dijkstra中dis[i]记录的是V0到i的最短距离。
用这样的for循环来更新dis,结果dis[j]是比较源点V0直接到j 和 源点V0经过k到j的最短距离所得结果
for(j = 1; j <= n; j++)
{
if ( !visit[j] && dis[j] > dis[k] + map[k][j])
{
dis[j] = dis[k] + map[k][j];
}
}
而prim中Len[i]记录的是顶点集U(看成整体)到i的最短距离
用这样的for循环来更新顶点集U到V-U中任一顶点的距离，比较的是加入k之前顶点集到j的距离 和 k 到j的距离 。
得到的就是包含k的新顶点集U到j的最短距离。 （感谢罗康琦大牛！！！）
//i=1时，U中只有起点xx和新加入的k，Len[j]与prim[j]比较：就是比较xx到j的距离和新加入U的k顶点到j的距离
//之后，Len[j]就是U到j的最短距离啦，这样把U中所有顶点看成一个，Len[j]就是U到j(V-U中任意一个)的最短距离
//以此类推，i>1 时，每次都把原来的顶点集U到j的距离和新加入的k到j的距离比较，这样得到了新U到j的最短距离
//从而,就得到了新U到V-U中任一顶点的距离，保存在 Len中
for (j = 1; j <= n; j++)
{
if ( !visit[j] && Len[j] > prim[k][j])
{
Len[j] = prim[k][j];
}
}
他们的区别就知道了。所以不能互用啊，prim还是乖乖算最小生成树吧，dijkstra还是继续管计算最短路径吧
举个例子就知道他们不能乱来了：
有四个顶点(v0,
v1, v2, v3)和四条边且边值定义为(v0,
v1)=20, (v0, v2)=10, (v1, v3)=2, (v3, v2)=15的图，用Prim算法得到的最小生成树中v0跟v1是不直接相连的，也就是在最小生成树中v0v1的距离是v0->v2->v3->v1的距离是27，而用Dijkstra算法得到的v0v1的距离是20，也就是二者直接连线的长度。
SO。。。。