#include<fstream>
using namespace std;
int d[200],hash[200],n,w[200][200],queue[2000];
ifstream infile;
ofstream outfile;
void function();
int max(int a,int b)
{
   if (a>=b)
   return a;
   else return b;
}
int main()
{
     
     infile.open("data.in",ios::in);
     outfile.open("data.out",ios::out);
     int i,m,j,u,v;
     do
     {
       infile>>n;
       if (n!=0)
       {
        memset(w,0,sizeof(w));
        for (i=1;i<=n;i++)
        {
           infile>>m;
           for (j=1;j<=m;j++)
           {
              infile>>u>>v;
              w[i][u]=v;
           }
        }
        function();
       }
     }while(n!=0);
     infile.close();
     outfile.close();
}
void function()
{
     
     int i,j,u,v,tou,wei,ans[101],ANS=214000,ANSi;
     memset(ans,214000,sizeof(ans));
     for (i=1;i<=n;i++)
     {
         memset(d,0,sizeof(d));
         memset(hash,0,sizeof(hash));
         memset(queue,0,sizeof(queue));
         for (j=0;j<=n;j++)
         d[j]=214000;
         d[i]=0;
         tou=0;wei=0;
         queue[wei++]=i;hash[i]=1;
         while (tou<wei)
         {
            u=queue[tou++];hash[u]=0;
            for (v=1;v<=n;v++)
            if (d[v]>d[u]+w[u][v]&&w[u][v]>0)
            {
               d[v]=d[u]+w[u][v];
               if(hash[v]==0)
               {hash[v]=1;queue[wei++]=v;}
            }
         }
         for (v=1;v<=n;v++)
         ans[i]=max(d[v],ans[i]);
     }
     for (i=1;i<=n;i++)
     if (ANS>ans[i])
     {ANS=ans[i];ANSi=i;}
     if (ANS==214000)
     outfile<<"disjoint"<<endl;
     else
     outfile<<ANSi<<' '<<ANS<<endl;
}

• Re:嘿嘿，第一次在POJ上一次AC，就是做N次SPFA，取最小值啦 (11) symons 2013-05-14 20:51:39
• Re:嘿嘿，第一次在POJ上一次AC，就是做N次SPFA，取最小值啦 (1829) rooney1314521 2014-09-21 10:01:10