一开始编的，觉得应该也可以啊
发现大家都用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");
}

• floyed更好吧 (2191) ecjtubaowp 2007-05-03 17:42:55
  • Re:floyed更好吧 (33) vigour 2007-05-03 19:18:58