go to play.txt

来自「以前ACM在哈工程HRBEU做的一些简单题目」· 文本 代码 · 共 75 行

#include <iostream.h>
#include <memory.h>
struct pp
{
       long a,d;
}p[60][60];
int main()
{
    long total,len[60],max,number,temp;
    bool color[60],flag;
    long m,n,x,y,z;
    long q[10000],f,r,i,j,k,t;
    long d[60];
    cin>>total;
    while(total--)
    {
              cin>>m>>n;
              flag=false;
              for(i=0;i<50;i++)len[i]=0;
               for(i=0;i<n;i++)
              {
                  cin>>x>>y>>z;
                  p[x][len[x]].a=y;
                  p[x][len[x]++].d=z;
                  p[y][len[y]].a=x;
                  p[y][len[y]++].d=z;
              }
              max=60000;
                for(i=0;i<m;i++)
              {
                 memset(color,1,sizeof(bool)*50);
                 for(k=0;k<m;k++)d[k]=0;
                 f=0;
                 r=-1;
                 q[++r]=i;
                 color[i]=false;
                 while(f<=r)
                 {
                    t=q[f];
                    f++;
                    for(j=0;j<len[t];j++)
                       if(color[p[t][j].a]==true)
                       {
                          color[p[t][j].a]=false;
                          d[p[t][j].a]=d[t]+p[t][j].d;
                          q[++r]=p[t][j].a;
                       }
                      else
                      {
                          if(d[p[t][j].a]>d[t]+p[t][j].d)
                          {
                            d[p[t][j].a]=d[t]+p[t][j].d;
                            q[++r]=p[t][j].a;
                          }   
                      }                           
                 }
                 if(i==0)for(k=0;k<m;k++)if(color[k]==true){flag=true;break;}
                 temp=d[i];                 
                 for(k=0;k<m;k++)if(temp<d[k])temp=d[k];
                 if(temp<max){max=temp;number=i;}
              }
              if(flag)cout<<"No solution."<<endl;
              else  cout<<number<<endl;
         }
         return 0;
}