Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:为什么Dijkstra算法RE,spfa,floyd都过了

Posted by 40475009H at 2018-11-16 09:14:27 on Problem 1847 and last updated at 2018-11-16 09:19:29
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator