AcWing 851. spfa求最短路

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 851. spfa求最短路原题链接简单

作者：

Bug-Free , 2021-03-29 01:15:46 , 所有人可见 , 阅读 2443

23

12

代码

#include <cstring>
#include <iostream>
#include <queue>

using namespace std;

const int N = 1e5 + 10;

int n, m;
int head[N], e[N], ne[N], w[N], idx;
bool st[N];
int dist[N];

void add(int a, int b, int c)
{
    e[idx] = b;
    w[idx] = c;
    ne[idx] = head[a];
    head[a] = idx++;
}

int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    queue<int> q;
    q.push(1);

    st[1] = true;  //判重数组， 队列中有重复的点没有意义

    while (q.size()) {
        int t = q.front();
        q.pop();

        st[t] = false;

        for (int i = head[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                if (!st[j]) {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    if (dist[n] == 0x3f3f3f3f) {
        return -1;
    }
    return dist[n];
}

int main()
{
    cin >> n >> m;

    memset(head, -1, sizeof head);

    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }

    int t = spfa();

    if (t == -1) {
        cout << "impossible" << endl;
    }
    else {
        cout << dist[n] << endl;
    }

    return 0;
}

8 评论

猫宁 2021-11-11 11:58

你好现在这个代码过不了了

猫宁 2021-11-11 12:20

找到原因了：数据加强了，存在最短路径为-1的情况

ustinian_09 2023-10-29 21:48 回复了猫宁的评论

然后怎么处理的啊

Mr.Yang 6个月前

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
using namespace std;
const int N=1e6+100;
int nxt[N],head[N],tot,len[N],val[N];
int n,m,dis[N];
bool bol[N],flag=0;
queue<int> q;
inline void add(int a,int b,int l)
{
    val[tot]=b;len[tot]=l;
    nxt[tot]=head[a];
    head[a]=tot++;
}
inline void SPFA()
{
    while(!q.empty())
    {
        int top=q.front();q.pop();
        bol[top]=false;
        for(int i=head[top];i!=-1;i=nxt[i])
        {
            int point=val[i];
            if(dis[point]>dis[top]+len[i])
            {
                dis[point]=dis[top]+len[i];
                if(bol[point]==false)
                {
                    q.push(point);bol[point]=true;
                }
            }
        }
    }
    if(dis[n]==0x3f3f3f3f)
    {
        flag=false;
    }
    else
    {
        flag=true;
    }
    return ;
}
signed main()
{
    memset(head,-1,sizeof(head));
    memset(dis,0x3f,sizeof(dis));
    cin>>n>>m;dis[1]=0;bol[1]=1;q.push(1);
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }
    SPFA();
    if(flag==true)
    {
        cout<<dis[n]<<endl;
    }
    else
    {
        cout<<"impossible"<<endl;
    }
    return 0;
}

这是数据加强后可以水过的代码