stockbroker grapevine.txt

以前ACM在哈工程HRBEU做的一些简单题目

#include <iostream>
using namespace std;
int stockman[100][100],d[100],n,p,c;
bool color[10],flag;
void visit(int h)
{
     int q[10000],f=0,r=-1,i,t;
     memset(color,1,n);
     memset(d,0,sizeof(d));
     color[h]=false;
     q[++r]=h;
     while(f<=r)
     {
     t=q[f++];
     for(i=0;i<n;i++)
     if(stockman[t][i]!=0)
     {
       if(color[i]==true)
       {
         color[i]=false;                
         d[i]=d[t]+stockman[t][i];
         q[++r]=i;
       }
       else
       {
           if(d[i]>d[t]+stockman[t][i])
           {
            d[i]=d[t]+stockman[t][i];
            q[++r]=i;
           }
       }
     }
     } 
     for(i=0;i<n;i++)if(color[i]==true)break;
     if(i>=n)
     {
             flag=false;
             t=d[0];
             for(i=1;i<n;i++)if(d[i]>t)t=d[i];
             if(c>t){c=t;p=h;}
     }
}    
int main()
{
  int n1,x,y,i;
  while(cin>>n&&n!=0)
  {
    memset(stockman,0,sizeof(stockman));
    for(i=0;i<n;i++)
    {
     cin>>n1;
     while(n1--){cin>>x>>y;stockman[i][x-1]=y;}
    }
    flag=true;
    c=10000;
    for(i=0;i<n;i++)visit(i);
    if(flag)cout<<"disjoint"<<endl;
    else cout<<p+1<<" "<<c<<endl;
   }
   return 0;
}