POJ 1125 C++ （圖論）

//別人五分鐘能敲出來的題，我卻做了五個小時，差距大的嚇人
//一眼就可以看出來用folyd_warshell,我卻用dijkstra，調試了N久
//首先引進一個輔助向量d[i]表示當前所找到的從起點 v到每個終點的最短路徑的長度.
它的初態(tài)為:若從v到vi有狐,則d[i]為弧上的權.否則d[i]為inifity.顯然有  
//一條最短路徑或者是弧(s,x),或者是中間只經(jīng)過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 蝸牛 閱讀(776) 評論(0)  編輯 收藏 引用 所屬分類: ACM ICPC