POJ 1125 C++ （图论）

//别人五分钟能敲出来的题，我却做了五个小时，差距大的吓人
//一眼就可以看出来用folyd_warshell,我却用dijkstra，调试了N久
//首先引进一个辅助向量d[i]表示当前所找到的从起点 v到每个终点的最短路径的长度.
它的初态为:若从v到vi有狐,则d[i]为弧上的权.否则d[i]为inifity.显然有  
//一条最短路径或者是弧(s,x),或者是中间只经过s的顶点而最后到达顶点x的路径.所以
//d[x]=min{d[x],d[s]+arcs[s][x]}

#include<iostream>
using namespace std;
int used[101],map[101][101],d[101],n,flag,max1,max2,v;
void solve(int i)
{ int j,k,min,v0,v1;
  for(j=1;j<=n;j++)
      {  used[j]=0;
         if(map[i][j]==0)
            d[j]=1000000000;
         else
            d[j]=map[i][j];
      }      

     used[i]=1;
      while(1)
      { min=1000000000;
        v0=0;
        for(j=1;j<=n;j++)
            { if(used[j]==0 && d[j]<min)
                 {min=d[j];
                   v0=j;
                  }
            }
       if(v0==0)
           break;
       used[v0]=1;
       for(j=1;j<=n;j++)    
           {if(used[j]==0 &&  map[v0][j] && min+map[v0][j]<d[j])
                d[j]=min+map[v0][j];
           }          
     }


   max1=0;
  for(k=1;k<=n;k++)
       { if(k==i)
           continue;
         if(d[k]>max1)
           {max1=d[k];
            v1=i;
           }
        }    

    if(max1<max2)
       {     flag=1;
             v=v1;      
             max2=max1;
       }  
}    

int main()
{ int m,i,j,a,b;
       freopen("in.txt","r",stdin);
       freopen("out.txt","w",stdout);
   while(cin>>n,n!=0)
       {  memset(map,0,sizeof(map));

          flag=0;
          for(i=1;i<=n;i++)
              { cin>>m;
               for(j=1;j<=m;j++)
                   { cin>>a>>b;
                     map[i][a]=b;
                   }
              }
      max2=1000000000;
      v=0;
      for(i=1;i<=n;i++)  
            solve(i);
      if(n==1)
          {  flag=1;
              v=1;
              max2=0;
           }
       if(flag)
          cout<<v<<" "<<max2<<endl;
       else
          cout<<"disjoint"<<endl;            

        }

    return 0;          
}    

posted on 2008-11-27 00:19 蜗牛 阅读(734) 评论(0)  编辑 收藏 引用 所属分类: ACM ICPC