floyd多源最短路径
#include<iostream> #include<cstring> #include<cstdio> #define inf 20 using namespace std; int dis[110][110]; int i,j,k,n; void floyd() { for(k=1; k<=n; ++k) for(i=1; i<=n; ++i) for(j=1; j<=n; ++j) if(i!=j && dis[i][j] > dis[i][k] +dis[k][j]) dis[i][j]=dis[i][k]+dis[k][j]; int maxlen; int min_max=ainf; int flag; for(i=1; i<=n; ++i) { maxlen=0; for(j=1; j<=n; ++j) if(i!=j && maxlen<dis[i][j]) maxlen=dis[i][j]; if(min_max>maxlen) { min_max=maxlen; flag=i; } } if(min_max<inf) cout<<flag<<' '<<min_max<<endl; else cout<<"disjoint"<<endl; } int main() { while(cin>>n&&n) { memset(dis,inf,sizeof(dis)); for(i=1; i<=n; ++i) { int m; cin>>m; for(j=1; j<=m; ++j) { int cat,time; cin>>cat>>time; dis[i][cat]=time; } } floyd(); } }