526互联

spfa求最短路——BFS，数组实现邻接表，数组实现队列

发布时间 2023-04-10 14:33:59作者: 杨五岁

题目描述

题目来源 AcWing

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出impossible。
数据保证不存在负权回路。
输入格式
第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式
输出一个整数，表示 1号点到 n 号点的最短距离。

如果路径不存在，则输出 impossible。

数据范围
\(1≤n,m≤10^5,\)
图中涉及边长绝对值均不超过 10000。
输入样例

3 3
1 2 5
2 3 -3
1 3 4

输出样例

2

代码

#include <iostream>
#include <fstream>
#include <cstring>
#include <memory>

using namespace std;

static const int N = 1e5 + 5;
static int idx = 1, e[N], ne[N], h[N], w[N], dist[N], que[N];
static bool foot[N];

/**
 * @brief 插入值到数组邻接表中
 * e存储节点编号，ne存储下一个节点的id，w存储节点权重，h存储头节点
 */
void insert(int x, int y, int z)
{
    e[idx] = y;
    ne[idx] = h[x];
    w[idx] = z;
    h[x] = idx++;
}

void spfa()
{
    int hh, tt;
    hh = tt = 0;
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    que[tt++] = 1;
    foot[1] = true;

    while (hh != tt)
    {
        int node_num = que[hh++];
        foot[node_num] = false;
        for (int node = h[node_num]; e[node]; node = ne[node])
        {
            if (dist[e[node]] > dist[node_num] + w[node]) /** 松弛操作 */
            {
                dist[e[node]] = dist[node_num] + w[node];
                if (!foot[e[node]])
                {
                    foot[e[node]] = true;
                    que[tt++] = e[node];
                }
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef LOCAL_DEBUG
    ifstream ifs ("./input.txt");
    cin.rdbuf(ifs.rdbuf());
#endif
// === coding here ===

    int n, m;
    cin >> n >> m;
    int x, y, z;
    while (m--)
    {
        cin >> x >> y >> z;
        insert(x, y, z);
    }
    spfa();
    if (dist[n] >= 0x3f3f3f3f)
        cout << "impossible" << endl;
    else
        cout << dist[n] << endl;

// === coding end  ===
    return EXIT_SUCCESS;
}