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

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

Posted by xijunlee93 at 2012-12-05 20:46:17 on Problem 1125
```#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:

User ID:
Title:

Content: