#include<iostream>
using namespace std;
#define maxint 10000
int p,c[100][100];
int Dijkstra(int v){
     int t,dist[100],k,newdist=10000;
	 bool s[100];
	 int temp = maxint,last=0;
	 for(t=1;t<=p;t++){               
	   dist[t] = c[v][t];
	   s[t] = false;
	 }
     s[v] = true;
	 for(t=1;t<p;t++){
	   int u = v;
        for(k=1;k<=p;k++)
			if((!s[k])&&(dist[k]<temp)) {u = k;temp = dist[k];}
		s[u] = true;
		for(k=1;k<=p;k++){
			if((!s[k])&&(c[u][k]<maxint)) {newdist = dist[u] + c[u][k];
			if(newdist<dist[k]) dist[k] = newdist;}
		}
	  }
	 
	 for(t=1;t<=p;t++){
		// cout<<dist[t];
		 if(dist[t]==maxint) return 0;
		   if(dist[t]>last) last = dist[t];
		   }
	 return last;
}
int main(){
    int n,i,t,time,y,j;
	while(cin>>p){
	  if(p==0) break;
	  
	  for(i=1;i<=p;i++){                   
		  for(t=1;t<=p;t++){
		    if(i==t) c[i][t] = 0;
			else c[i][t] = maxint;
		  }
	  }
      for(i=1;i<=p;i++){
	    cin>>n;                
		for(t=1;t<=n;t++){
             cin>>j>>time;      
			 if(i==j) c[i][j] = 0;
			 else c[i][j] = time;
		}
	  }
	  if(p==1) {cout<<"1"<<' '<<"0"<<endl;continue;}
	  int min = 10000,h;
	  for(i=1;i<=p;i++){
	     y = Dijkstra(i);
		 //cout<<"y:"<<y<<endl;
		 if(y==0) continue;
		 if(y<min) {min = y;h = i;}
	  }
	  if(min==10000) cout<<"disjoint"<<endl;
	  else cout<<h<<' '<<min<<' '<<endl;
   }
return 0;

}

• Re:各位大侠，帮我看一下代码，一直WA，却不知问题出在哪？？谢谢！！！不胜感激呀！！ (1549) 09122389 2011-04-15 19:19:17