SPFA为啥全RE

P4779 【模板】单源最短路径（标准版）

航小怕 @ 2024-01-27 19:55:14

样例过了，但是全RE（悲 代码：```cpp

include <stdio.h> //Dijkstra

include <string.h>

include <queue>

include <iostream>

using namespace std; int n,m,s,num=0,dis[11451]={0}; int head[11451]={0}; bool vis[11451]={0}; struct Edge{ int from; int to; int Next; int Distance; }edge[21451]; void AddEdge(int From,int To,int Dis){ edge[++num].Next=head[From]; head[From]=num; edge[num].from=From; edge[num].to=To; edge[num].Distance=Dis; return; } int main(){

scanf("%d%d%d",&n,&m,&s);
for(int i=0;i<m;i++){
    int u,v,d;
    scanf("%d%d%d",&u,&v,&d);
    AddEdge(u,v,d);
}
memset(dis,0x3f,sizeof(dis));
queue<int>qu;
qu.push(1);
dis[1]=0;
vis[1]=1;
while(!qu.empty()){
    int Now=qu.front();
    qu.pop();vis[Now]=0;
    for(int i=head[Now];i;i=edge[i].Next){
        if(dis[edge[i].to]>dis[Now]+edge[i].Distance){
            dis[edge[i].to]=dis[Now]+edge[i].Distance;
            if(!vis[edge[i].to]){
                vis[edge[i].to]=1;
                qu.push(edge[i].to);
            }
        }
    }
}
for(int i=1;i<=n;i++){
    printf("%d ",dis[i]);
}
return 0;

}

by Wind_love @ 2024-01-27 20:22:27

@航小怕 可以上OI WIKI

by 航小怕 @ 2024-01-27 20:28:30

@hello_world_djh 用了堆优化，32pts，求改 2AC,3WA,1TLE 代码：

# include <stdio.h> //Dijkstra
# include <string.h>
# include <queue>
# include <iostream>
using namespace std;
int n,m,s,num=0,dis[1145100]={0};
int head[1145100]={0};
bool vis[1145100]={0};
struct dui{
    int id;
    int e;
     bool operator <(const dui &x)const
    {
        return x.e<e;
    }
};
struct Edge{
    int from;
    int to;
    int Next;
    int Distance;
}edge[2145100];
void AddEdge(int From,int To,int Dis){
    edge[++num].Next=head[From];
    head[From]=num;
    edge[num].from=From;
    edge[num].to=To;
    edge[num].Distance=Dis;
    return;
}
int main(){

    scanf("%d%d%d",&n,&m,&s);
    for(int i=0;i<m;i++){
        int u,v,d;
        scanf("%d%d%d",&u,&v,&d);
        AddEdge(u,v,d);
    }
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;
    priority_queue<dui>qu;
    qu.push({1,0});
    for(int i=0;i<n;i++){
        int Minn=0x7fffffff;
        dui sa=qu.top();
        int sd=sa.id;
        qu.pop();
                /*for(int j=1;j<=n;j++){
            if(dis[j]<Minn&&!vis[j]){
                Minn=dis[j];
                sd=j;
            } 
        }*/
        vis[sd]=1;
        for(int j=head[sd];j;j=edge[j].Next){
            if(dis[edge[j].to]>dis[sd]+edge[j].Distance){
                dis[edge[j].to]=dis[sd]+edge[j].Distance;
                qu.push({edge[j].to,dis[edge[j].to]});
            }
        }
    }
    for(int i=1;i<=n;i++){
        printf("%d ",dis[i]);
    }
    return 0;
}

by hello_world_djh @ 2024-01-27 20:43:25

@航小怕

给你改完了，需要改几处地方，我都用注释给你标出来了。

# include <stdio.h> //Dijkstra
# include <string.h>
# include <queue>
# include <iostream>
using namespace std;
int n,m,s,num=0,dis[1145100]={0};
int head[1145100]={0};
bool vis[1145100]={0};
struct dui{
    int id;
    int e;
     bool operator <(const dui &x)const
    {
        return x.e<e;
    }
};
struct Edge{
    int from;
    int to;
    int Next;
    int Distance;
}edge[2145100];
void AddEdge(int From,int To,int Dis){
    edge[++num].Next=head[From];
    head[From]=num;
    edge[num].from=From;
    edge[num].to=To;
    edge[num].Distance=Dis;
    return;
}
int main(){

    scanf("%d%d%d",&n,&m,&s);
    for(int i=0;i<m;i++){
        int u,v,d;
        scanf("%d%d%d",&u,&v,&d);
        AddEdge(u,v,d);
    }
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;//this
    priority_queue<dui>qu;
    qu.push({s,0});//this
    while(!qu.empty()){
        int Minn=0x7fffffff;
        dui sa=qu.top();
        int sd=sa.id;
        qu.pop();
                /*for(int j=1;j<=n;j++){
            if(dis[j]<Minn&&!vis[j]){
                Minn=dis[j];
                sd=j;
            } 
        }*/
        if(vis[sd]) continue;//this
        vis[sd]=1;
        for(int j=head[sd];j;j=edge[j].Next){
            if(dis[edge[j].to]>dis[sd]+edge[j].Distance){
                dis[edge[j].to]=dis[sd]+edge[j].Distance;
                qu.push({edge[j].to,dis[edge[j].to]});
            }
        }
    }
    for(int i=1;i<=n;i++){
        printf("%d ",dis[i]);
    }
    return 0;
}

by 航小怕 @ 2024-01-27 20:49:50

@hello_world_djh 感谢大佬，已经献上了关注

上一页 |