好久没有写题了，所以这一道简单题都错的离谱，调试了好久。
我先用Dijstra和Floyd分别写了一次，其实质差不多；只是Dijstra是一维，需要多次调用；而Floyd是二维，调用一次就行了。。。
大意：
以不同的点作为源点，找出此源点与其他各点的单源最短路径中的最大值，然后在这几个最大值中找出最小值，如果最后找出的最小值是定义的INF，就说明此图不连通，输出“disjoint”，否则输出是最大值最小的源点和该最大值中的最小值
我设计的测试数据：
1
0
3
1 2 3
2 1 2
0
0
预计结果：
1 0
disjoint
******************************************************************************************
#include<iostream>using namespace std;#define DEBUG 1
const int MaxSize=101,INF=10001;int Map[MaxSize][MaxSize],dis[MaxSize];bool used[MaxSize];int num;
void init(){ int i,j; for( i=1; i<=num; ++i ){ for( j=i; j<=num; ++j ){ Map[i][j] = Map[j][i] = INF ;} Map[i][i] = 0 ; } }
void Dijstra(int n){ int i,j,index,Min; for(i=1;i<=num;i++){ dis[i]=Map[n][i]; used[i]=false;} used[n]=true; index=n; for(i=1;i<=num;i++){ Min=INF; for(j=1;j<=num;j++){ if(!used[j]&&Min>=dis[j]){ Min=dis[j]; index=j;} } used[index]=true; for(j=1;j<=num;j++){ if(!used[j]&&dis[j]>(dis[index]+Map[index][j])) dis[j]=dis[index]+Map[index][j];} }}
int main(){ #if DEBUG freopen("C:\\Documents and Settings\\Administrator\\桌面\\in.txt","r",stdin); freopen("C:\\Documents and Settings\\Administrator\\桌面\\out.txt","w",stdout); #endif int contacts,time,i,j,k,m,len,q,index; while(cin>>num){ if(num==0)break; init(); k=1;q=INF; //输入数据 while(k<=num){ cin>>m; for(i=0;i<m;i++){ cin>>contacts>>time; Map[k][contacts]=time;} k++;} //处理数据 for(i=1;i<=num;i++){ Dijstra(i); len=0; for(j=1;j<=num;j++){ if(len<dis[j])len=dis[j]; } if(q>len){ q=len; index=i;} } //输出结果 if(q==INF)cout<<"disjoint"<<endl; else cout<<index<<" "<<q<<endl; } return 0;}
*********************************************************************************************
************************************************************************************************
#include<iostream>using namespace std;
#define DEBUG 0
const int MaxSize=101,INF=10001;int Map[MaxSize][MaxSize],G[MaxSize][MaxSize];int num;
void init(){ int i,j; for( i=1; i<=num; ++i ){ for( j=i; j<=num; ++j ){ Map[i][j] = Map[j][i] = INF ;} Map[i][i] = 0 ; } }
void Floyd(){ int i,j,k; for(i=1;i<=num;i++) for(j=1;j<=num;j++) G[i][j]=Map[i][j]; for(k=1;k<=num;k++){ for(i=1;i<=num;i++){ for(j=1;j<=num;j++){ if(G[i][k]<INF&&G[k][j]<INF&&G[i][j]> (G[i][k]+G[k][j])) G[i][j]=G[i][k]+G[k][j]; } } }}
int main(){ #if DEBUG freopen("C:\\Documents and Settings\\Administrator\\桌面\\in.txt","r",stdin); freopen("C:\\Documents and Settings\\Administrator\\桌面\\out.txt","w",stdout); #endif int contacts,time,m,q,i,j,k,min,index; while(cin>>num){ if(num==0)break; init(); k=1; while(k<=num){ cin>>m; for(i=0;i<m;i++){ cin>>contacts>>time; Map[k][contacts]=time;} k++; } Floyd(); q=INF; for(i=1;i<=num;i++){ min=0; for(j=1;j<=num;j++){ if(G[i][j]>min) min=G[i][j]; } if(q>min){ q=min; index=i;} } if(q==INF) cout<<"disjoint"<<endl; else cout<<index<<" "<<q<<endl; } return 0;}
转载于:https://www.cnblogs.com/miaycl/archive/2010/07/28/1786568.html
相关资源：JAVA上百实例源码以及开源项目