其他板子

$题目链接:$
https://www.acwing.com/problem/content/853/
自行尝试

$主要是这个结构体:$

struct SPFA {
    int n; // 图的节点数
    std::vector<std::vector<std::pair<int, int>>> adj; // 邻接表，存储图的边
    std::vector<int> dist; // 存储起点到各个节点的最短距离
    std::vector<int> cnt; // 记录每个节点入队的次数，用于判断是否存在负环
    std::vector<bool> in_queue; // 标记节点是否在队列中
    std::queue<int> q; // 存储当前需要更新的节点

    SPFA(int n) : n(n), adj(n), dist(n, INT_MAX), cnt(n, 0), in_queue(n, false) {} 
    // 构造函数，初始化各个变量

    void add_edge(int u, int v, int w) { // 添加一条边
        adj[u].emplace_back(v, w); // u -> v 的边权为 w
    }

    bool run(int s) { // 执行 SPFA 算法，s 为起点
        dist[s] = 0; // 起点到自己的距离为 0
        in_queue[s] = true; // 将起点加入队列
        q.push(s); // 将起点加入队列
        while (!q.empty()) { // 当队列不为空时
            int u = q.front(); // 取出队首节点
            q.pop(); // 弹出队首元素
            in_queue[u] = false; // 标记该节点不在队列中
            for (auto [v, w] : adj[u]) { // 遍历 u 的所有邻居节点
                if (dist[v] > dist[u] + w) { // 如果起点到 v 的距离可以通过 u 更新
                    dist[v] = dist[u] + w; // 更新起点到 v 的最短距离
                    cnt[v]++; // 记录 v 入队的次数
                    if (cnt[v] >= n) return false; // 如果存在负环，则返回 false
                    if (!in_queue[v]) { // 如果 v 不在队列中，则将其加入队列
                        q.push(v);
                        in_queue[v] = true;
                    }
                }
            }
        }
        return true; // 如果不存在负环，则返回 true
    }
};

#include<bits/stdc++.h>

struct SPFA {
    int n; // 图的节点数
    std::vector<std::vector<std::pair<int, int>>> adj; // 邻接表，存储图的边
    std::vector<int> dist; // 存储起点到各个节点的最短距离
    std::vector<int> cnt; // 记录每个节点入队的次数，用于判断是否存在负环
    std::vector<bool> in_queue; // 标记节点是否在队列中
    std::queue<int> q; // 存储当前需要更新的节点

    SPFA(int n) : n(n), adj(n), dist(n, INT_MAX), cnt(n, 0), in_queue(n, false) {} 
    // 构造函数，初始化各个变量

    void add_edge(int u, int v, int w) { // 添加一条边
        adj[u].emplace_back(v, w); // u -> v 的边权为 w
    }

    bool run(int s) { // 执行 SPFA 算法，s 为起点
        dist[s] = 0; // 起点到自己的距离为 0
        in_queue[s] = true; // 将起点加入队列
        q.push(s); // 将起点加入队列
        while (!q.empty()) { // 当队列不为空时
            int u = q.front(); // 取出队首节点
            q.pop(); // 弹出队首元素
            in_queue[u] = false; // 标记该节点不在队列中
            for (auto [v, w] : adj[u]) { // 遍历 u 的所有邻居节点
                if (dist[v] > dist[u] + w) { // 如果起点到 v 的距离可以通过 u 更新
                    dist[v] = dist[u] + w; // 更新起点到 v 的最短距离
                    cnt[v]++; // 记录 v 入队的次数
                    if (cnt[v] >= n) return false; // 如果存在负环，则返回 false
                    if (!in_queue[v]) { // 如果 v 不在队列中，则将其加入队列
                        q.push(v);
                        in_queue[v] = true;
                    }
                }
            }
        }
        return true; // 如果不存在负环，则返回 true
    }
};

signed main() {
    int n, m;
    std::cin >> n >> m;
    SPFA spfa(n);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        std::cin >> u >> v >> w;
        spfa.add_edge(u - 1, v - 1, w); // 将节点编号从1开始转换为从0开始
    }
    if (spfa.run(0)) { // 如果起点到各个节点的最短距离已经求出

        if (spfa.dist[n - 1] == INT_MAX) { // 如果终点不可达
            std::cout << "impossible" << std::endl;
        } 
        else {
            std::cout << spfa.dist[n - 1] << std::endl; // 输出起点到终点的最短距离
        }
    } 
    else { // 如果存在负环
        std::cout << "impossible" << std::endl;
    }
    return 0;
}