| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
啊啊啊啊,为什么啊,Dijkstra无限WA啊,Floyd一次AC,谁帮我看下Dj的算法错在哪里啊#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int INF = 99999999;
const int maxn = 220;
int e[maxn][maxn],dis[maxn],i,j,book[maxn],minn,tmp;
int u,v;
int n,start,eend,m,t1,t2,t3;
int main()
{
// freopen("in.txt","r",stdin);
while(scanf("%d %d %d",&n,&start,&eend)!=EOF){
for(i=1;i<=n;i++){
dis[i]=INF;
for(j=1;j<=n;j++)
if(i==j)
e[i][j]=0;
else
e[i][j]=INF;
}
for(i=1;i<=n;i++){
scanf("%d",&m);
for(j=1;j<=m;j++){
scanf("%d",&t1);
if(j==1)
e[i][t1]=0;
else
e[i][t1]=1;
}
}
for(i=1;i<=n;i++)
dis[i]=e[start][i];
dis[start]=0;
memset(book,0,sizeof(book));
book[start]=1;
for(i=1;i<=n;i++){
minn=INF;
for(j=1;j<=n;j++){
if(book[j]==0&&dis[j]<minn){
minn=dis[j];
u = j;
}
}
book[u]=1;
for(v=1;v<=n;v++){
if(e[u][v]<INF){
if(dis[v]>dis[u]+e[u][v])
dis[v]=dis[u]+e[u][v];
}
}
}
if(dis[eend]<INF)
printf("%d\n",dis[eend]);
else
cout<<"-1"<<endl;
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator