求助大佬帮忙看一下spfa只过了一个点,其他全是RE

回复帖子

@cooronx 2019-05-14 18:18 回复
#include<iostream>
#include<algorithm>
#include<queue>
#define INF 999999999;
using namespace std;
int n,m,s,u,v,w;
int t;
int head[100000],dis[1000000];
bool vis[1000000];
struct map{
    int next,to,w;
}h[10000];
queue<int> q;
void re_boot(int u,int v,int w){
    ++t;
    h[t].next=head[u];
    h[t].to=v;
    h[t].w=w;
    head[u]=t;
}
void spfa(){
    int u,v;
    for(int i=1;i<=n;++i){
        dis[i]=INF;
    }
    q.push(s);
    dis[s]=0;
    while(!q.empty()){
        u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=h[i].next){
            v=h[i].to;
            if(dis[v]>dis[u]+h[i].w){
                dis[v]=dis[u]+h[i].w;
                if(!vis[v]){
                   vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
}
int main(){
    cin>>n>>m>>s;
    for(int i=1;i<=m;++i){
        cin>>u>>v>>w;
        re_boot(u,v,w);
    }
    spfa();
    for(int i=1;i<=n;++i){
        cout<<dis[i]<<" ";
    }
    return 0;
} 
@cooronx 2019-05-14 18:19 回复 举报

然后这是题解的

#include<bits/stdc++.h>
#define maxn 10005
#define maxm 500005
#define inf 99999999
using namespace std;
int n,m,s,tot,dis[maxn],head[maxn];
bool vis[maxn];
struct Edge
{
      int next,to,w;
}h[maxm];
void add(int u,int v,int w)
{
    h[++tot].next=head[u];
    h[tot].to=v;
    h[tot].w=w;
    head[u]=tot;
}
//初始化队列 
queue<int> q;
 void spfa()
{
    for(int i=1; i<=n; i++)
    {
        dis[i]=inf;
    }
    int u,v;
    q.push(s);
    dis[s]=0;
    while(!q.empty())
    //当队列里没有元素的时候,那就已经更新了所有的单源最短路径
    {
        u=q.front();
        //将队手节点记录并弹出队首节点
        q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=h[i].next)
        //寻找与u相连的边
        {
            v=h[i].to;
            if(dis[v]>dis[u]+h[i].w)
            {
                dis[v]=dis[u]+h[i].w;
                //松弛操作,和floyd比较相似
                if(!vis[v])
                {
                //已经在队列里的点就不用再进入了
                      vis[v]=1;
                      q.push(v);
                }
            }
        }
    }
}
int main(){
    cin>>n;cin>>m;cin>>s;
    for(int i=1,u,v,w;i<=m;i++)
    {
        cin>>u;/*起点*/cin>>v;/*终点*/cin>>w;/*权值*/ 
        add(u,v,w);
    }
    spfa();
    for(int i=1; i<=n; i++)
    {
        cout<<dis[i]<<" ";
    }
    return 0;
}
@cooronx 2019-05-14 18:20 回复 举报

可以解释一下题解里的那个head数组和h的next是什么意思吗?-_- 谢谢啦

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。