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