求助SPFA

听取MLE声一片 @ 2020-09-29 22:34:22

by 听取MLE声一片 @ 2020-09-29 22:34:29

要改正的代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
using namespace std;
const int inf=2147483647;
int n,m,dis[500010],book[500010];
vector<int> a[500010],b[500010];
void add(int u,int v,int w){
    a[u].push_back(v);
    b[v].push_back(u);
}
void spfa(int s){
    queue<int> q;
    memset(book,0,sizeof(book));
    for(int i=0;i<=n;i++)
        dis[i]=inf;
    dis[s]=0;
    book[s]=1;
    q.push(s);
    while(!q.empty()){
        int p=q.front();
        q.pop();
        book[p]=0;
        for(int i=0;i<a[p].size();i++){
            int x=a[p][i],y=b[p][i];
            if(dis[x]>dis[p]+y){
                dis[x]=dis[p]+y;
                if(!book[x]){
                    q.push(x);
                    book[x]=1;
                }
            }
        }
    }
}
int main()
{
    int s;
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);
    }
    spfa(s);
    for(int i=1;i<=n;i++)
        cout<<dis[i]<<' ';
    return 0;
}

邻接表AC代码

#include<bits/stdc++.h>
using namespace std;
int n,m,s,Edgecnt;
int head[510010],edge[510010];
int nxt[500010],to[500010];
int dis[50010],vis[50010];
queue<int> q;
void add(int u,int v,int w){
    Edgecnt++;
    to[Edgecnt]=v,edge[Edgecnt]=w;
    nxt[Edgecnt]=head[u],head[u]=Edgecnt;
}
void spfa(){
    memset(vis,0,sizeof(vis));
    memset(dis,0x3f3f3f3f,sizeof(dis));
    dis[s]=0;vis[s]=1;q.push(s);
    while(!q.empty()){
        int x=q.front();q.pop();
        vis[x]=0;
        for(int i=head[x];i;i=nxt[i]){
            int tmp=to[i],val=edge[i];
            if(dis[tmp]>dis[x]+val){
                dis[tmp]=dis[x]+val;
                if(!vis[tmp]){
                    q.push(tmp);
                    vis[tmp]=1;
                }
            }
        }
    }
}
int main(){
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        int from,to,val;
        cin>>from>>to>>val;
        add(from,to,val);
    }
    spfa();
    for(int i=1;i<=n;i++) {
        if(dis[i]!=0x3f3f3f3f) cout<<dis[i]<<" ";
        else cout<<2147483647<<" ";
    }
    return 0;
}

by 7KByte @ 2020-09-29 22:37:18

@听取MLE声一片 你这建的是双向边吧

by Shiroko @ 2020-09-29 22:37:46

用Dijkstra+堆优化+链式前向星不香吗

by 听取MLE声一片 @ 2020-09-29 22:43:14

@Inf_Voltage 谢谢！除了这个以外建图有一处错误，已AC，感谢！