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 |
Re:为什么Dijkstra算法RE,spfa,floyd都过了In Reply To:为什么Dijkstra算法RE,spfa,floyd都过了 Posted by:hurmishine at 2016-07-29 15:20:59 > #include <iostream> > #include <cstdio> > #include <queue> > using namespace std; > const int INF=0x3f3f3f3f; > int a[200][200]; > int dis[200]; > bool vis[200]; > int n,s,t; > void Dij() > { > for(int i=1; i<=n; i++) > { > dis[i]=a[s][i]; > vis[i]=false; > } > vis[s]=true; > dis[s]=0; > for(int i=1; i<=n; i++) > { > int minn=INF; > int p; > for(int j=1; j<=n; j++) > { > if(!vis[j]&&dis[j]<minn) > { > minn=dis[j]; > p=j; > } > } > vis[p]=true; > //if(minn==INF) break; > for(int j=1; j<=n; j++) > { > if(!vis[j]&&dis[j]>dis[p]+a[p][j]) > dis[i]=dis[p]+a[p][j]; > } > } > } > void floyd() //floyd 算法 > { > for (int i = 1; i <= n; ++ i) > { > for (int j = 1; j <= n; ++ j) > { > for (int k = 1; k <= n; ++ k) > { > if (a[j][k] > a[j][i] + a[i][k]) > { > a[j][k] = a[j][i] + a[i][k]; > } > } > } > } > if (a[s][t] >= INF) > { > printf("-1\n"); > } > else > printf("%d\n", a[s][t]); > } > void spfa() > { > for(int i=1;i<=n;i++) > { > dis[i]=INF; > vis[i]=false; > } > dis[s]=0; > vis[s]=true; > queue<int>q; > q.push(s); > while(!q.empty()) > { > int p=q.front(); > q.pop(); > vis[p]=false;///!!!!!! > for(int i=1;i<=n;i++) > { > if(dis[i]>dis[p]+a[p][i]) > { > dis[i]=dis[p]+a[p][i]; > if(!vis[i]) > { > vis[i]=true; > q.push(i); > } > } > } > } > } > int main() > { > while(cin>>n>>s>>t) > { > for(int i=1; i<=n; i++) > { > for(int j=1; j<=n; j++) > if(i==j) a[i][j]=0; > else a[i][j]=INF; > } > int x,y,z; > for(int i=1; i<=n; i++) > { > scanf("%d",&x); > for(int j=0; j<x; j++) > { > scanf("%d",&y); > if(j==0) > a[i][y]=0; > else > a[i][y]=1; > } > } > //floyd(); > > Dij(); > //spfa(); > if(dis[t]<INF) > cout<<dis[t]<<endl; > else > cout<<"-1"<<endl; > } > return 0; > } This line is wrong dis[i]=dis[p]+a[p][j]; The correct line is dis[j]=dis[p]+a[p][j]; And you need to change int dis[200] to long long dis[200] and const int INF=0x3f3f3f3f to int INF=0x3f3f3f3f Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator