| ||||||||||
| 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