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 航小怕 @ 2024-01-27 19:55:40

# 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 hello_world_djh @ 2024-01-27 19:59:07

@航小怕 RE 的原因是数组开小了。

而且你使用的是 SPFA，而这个题是标准版。请使用 dijstra，SPFA 无法通过此题。

by 航小怕 @ 2024-01-27 20:02:47

@hello_world_djh 那为啥我用了Dijkstra也全部RE了代码：

# 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));
    dis[1]=0;
    for(int i=0;i<n;i++){
        int Minn=0x7fffffff,sd;
        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;
            }
        }
    }
    for(int i=1;i<=n;i++){
        printf("%d ",dis[i]);
    }
    return 0;
}

by 航小怕 @ 2024-01-27 20:11:02

懂了，数组开大一点了，但是Dijkstra全部TLE（悲，献上代码，大佬求调

# include <stdio.h> //Dijkstra
# include <string.h>
# include <queue>
# include <iostream>
using namespace std;
int n,m,s,num=0,dis[114510]={0};
int head[114510]={0};
bool vis[114510]={0};
struct Edge{
    int from;
    int to;
    int Next;
    int Distance;
}edge[214510];
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;
    for(int i=0;i<n;i++){
        int Minn=0x7fffffff,sd;
        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;
            }
        }
    }
    for(int i=1;i<=n;i++){
        printf("%d ",dis[i]);
    }
    return 0;
}

by Wind_love @ 2024-01-27 20:11:26

@航小怕数组开小了加个0 Dijskstra需要堆优化

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

楼上正解。

by 航小怕 @ 2024-01-27 20:13:42

@I_AK_IOI_1114 但还是TLE啊

by hello_world_djh @ 2024-01-27 20:14:01

@hello_world_djh 你写的这个 dijstra 是 \Theta (n^2) 的。堆优化可以做到 \Theta (n \log n)。

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

@hello_world_djh 不懂就问，怎么优化

by hello_world_djh @ 2024-01-27 20:15:34

@航小怕我讲的不太清楚，你最好百度。

| 下一页