2009-2-23-pku1125.txt

数据结构中的单元最短路径算法的题目和源代码！其中所有的题目都能在PKU上找的到！

/*
题目大意：
本题目求那个中转者发信息给其他所有人 的时间最快 
特别注意：一个人发信息给其他人，最快完成这项工作所需的时间  
             由时间花费最长那个决定
例如：最后的路径矩阵是：
1 2 3 
4 5 6
7 8 9
显然第一个人到其他所有人的最长时间是3
    第二个人到其他所有人的最长时间是6
	第三个人到其他所有人的最长时间是9
最后我输出的是：
    1 3
1表示第一个  3是第一个人完成信息发送的时间上限
*/
#include<stdio.h>
#include<string.h>
const int MAX=105;
const int INF=100005;
/*
多源最短路径，floyd_warshall算法，复杂度0(n^3)
求出所有点对之间的最短路径，传入图的大小和邻接阵
返回各个点间最短距离min[][]和路径pre[][],pre[i][j]记录i到j最短路径上j的父节点
可更改路权类型，路权必须非负！
*/
void Floyd_Warshall(int n,int mat[][MAX],int min[][MAX],int pre[][MAX])
{
	int i,j,k;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			min[i][j]=mat[i][j],pre[i][j]=(i==j)?-1:i;
	for(k=1;k<=n;k++)
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				if(min[i][k]+min[k][j]<min[i][j])
					min[i][j]=min[i][k]+min[k][j],pre[i][j]=pre[k][j];
}
int main()
{
	int i,j,n,ans,st,ed,distance,temp,m;
	int mat[MAX][MAX],min[MAX][MAX],pre[MAX][MAX];
	while(scanf("%d",&n),n)
	{
		for(i=1;i<=104;i++)
			for(j=1;j<=104;j++)
				mat[i][j]=INF;//将mat[][]开始初始化为INF，这个很重要！
		for(i=1;i<=n;i++)
		{
			mat[i][i]=0;//自身到自身的距离为0
			scanf("%d",&m);
			for(j=1;j<=m;j++)
			{
				scanf("%d%d",&ed,&distance);
				mat[i][ed]=distance;
			}
		}
		Floyd_Warshall(n,mat,min,pre);
		ans=INF;
		st=-1;
		for(i=1;i<=n;i++)
		{
			temp=-1;
			for(j=1;j<=n;j++)
				if(temp<min[i][j])
					temp=min[i][j];
			if(temp<ans)
			{
				ans=temp;
				st=i;
			}
		}
		if(st==-1)
			printf("disjoint\n");
		else
			printf("%d %d\n",st,ans);
	}
	return 0;
}
/*
3
2 2 4 3 5
2 1 2 3 6
2 1 2 2 2
5
3 4 4 2 8 5 3
1 5 8
4 1 6 4 10 2 7 5 2
0
2 2 5 1 5
0


3 2
3 10
*/