poj 1125 Stockbroker Grapevine
#include <iostream> #include <queue> #include <string> #include <stdio.h> using namespace std; int cost[102][102]; int n; void floyd(){ int i,j,k; for(k=1;k<=n;k++){ for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ if(cost[i][j]>cost[i][k]+cost[k][j]) cost[i][j]=cost[i][k]+cost[k][j]; } } } int p1=100*100*127; int q1=1; for(i=1;i<=n;i++){ k=0; for(j=1;j<=n;j++){ if(cost[i][j]!=0)k++; } if(k==n-1){ int p=0; for(j=1;j<=n;j++) if(cost[i][j]>p)p=cost[i][j]; if(p<p1){ p1=p; q1=i; } } } if(p1!=100*100*127)cout<<q1<<" "<<p1<<endl; else cout<<"disjoint"<<endl; } int main() { while(cin>>n&&n!=0){ int i,j; for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ if(i!=j)cost[i][j]=100*100*127; else cost[i][j]=0; } } for(j=1;j<=n;j++){ int m; cin>>m; int temp; for(i=1;i<=m;i++){ cin>>temp; cin>>cost[j][temp]; } } floyd(); } return 0; }