> 一开始编的，觉得应该也可以啊
> 发现大家都用Floyd-Warshall，不知道我这个怎么改？或者哪里行不通。。。
> 
> #include<iostream.h>
> using namespace std;
> #define MAX 102
> #define INF 200
> 
> int main()
> {
>     int n,c[MAX][MAX],num;
>     int time[MAX],prev[MAX],dist[MAX],minTime,maxTime,start;
>     int temp1,temp2,i,j,k,u,temp,newdist;
>     bool s[MAX];
> 
>     scanf("%d",&n);
>     while(n!=0)
>     {
>         for(i=1;i<=n;i++)
>           for(j=1;j<=n;j++)
>             c[i][j]=INF;
>         for(i=1;i<=n;i++)
>         {
>            scanf("%d",&num);
>            for(j=0;j<num;j++)
>            {
>               scanf("%d%d",&temp1,&temp2);
>               c[i][temp1]=temp2;
>            }
>         }
>         start=1;
>         minTime=10000000;
>         for(i=1;i<=n;i++)
>         {   
>             maxTime=0;
>             for(j=1;j<=n;j++)
>             {
>                dist[j]=c[i][j];
>                s[j]=false;
>                if(dist[j]==INF) prev[j]=0;
>                else  prev[j]=i;
>             }
>             dist[i]=0; s[i]=true; time[i]=0;
>             for(j=1;j<n;j++)
>             {
>                temp=INF;
>                u=i;
>                for(k=1;k<=n;k++)
>                   if(!s[k] && dist[k]<temp)
>                   {
>                      u=k;
>                      temp=dist[k];
>                   }
>                
>                if(temp==INF) break;
>                s[u]=true; time[u]=time[prev[u]]+temp; 
>                if(time[u]>maxTime) maxTime=time[u];
>                for(k=1;k<=n;k++)
>                   if(!s[k] && c[u][k]<INF)
>                   {
>                      newdist=dist[u]+c[u][k];
>                      if(newdist<dist[k])
>                      {
>                         dist[k]=newdist;
>                         prev[k]=u;
>                      }
>                   }
>             }
>             if(temp!=INF && maxTime<minTime){ minTime=maxTime; start=i; }
>         }
>         if(minTime==10000000) printf("disjoint\n");
>         else printf("%d %d\n",start,minTime);
>         scanf("%d",&n);
>     }
>     system("pause");
> }

• Re:floyed更好吧 (33) vigour 2007-05-03 19:18:58