Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## Re:嘿嘿，第一次在POJ上一次AC，就是做N次SPFA，取最小值啦

Posted by rooney1314521 at 2014-09-21 10:01:10 on Problem 1125
In Reply To:嘿嘿，第一次在POJ上一次AC，就是做N次SPFA，取最小值啦 Posted by:xijunlee93 at 2012-12-05 20:46:17
```> #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;
> }
```

Followed by: