$$\color{red}{算法}\color{blue}{基础课}\color{purple}{笔记and题解}\color{green}{汇总}$$

基于转移进行优化：
dist[b] = min(dist[b], dist[a] + w)
如果 dist[b] 想要变小，dist[a] 就要先变小，所以存一个队列，存储变小了的节点，用以更新后继。
所以算法流程是：

1. 只要队列里有元素，就取出队头。
2. 更新它的所有出边，a->b，如果 b 已经在队列中就不用再插入了。

基本思路就是“我更新过谁，我就拿谁来更新别人”。
长得很像 Dijkstra。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
#define fi first
#define se second
#define PII pair<int, int>
int h[N], e[N], w[N], ne[N], idx = 0;
int dist[N], n, m;
bool st[N];
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int spfa() {
    queue<PII> q;
    memset(dist, 0x3f3f3f3f, sizeof dist);
    dist[1] = 0;
    q.push({0, 1});
    st[1] = 1;
    while (q.size()) {
        PII p = q.front();
        q.pop();
        int t = p.se;
        st[t] = 0;
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[t]+ w[i]) {
                dist[j] = dist[t] + w[i];
                if (!st[j]) {
                    st[j]=1;
                    q.push({dist[j], j});
                }
            }
        }
    }
    if (dist[n] == 0x3f3f3f3f) return -0x3f3f3f3f;
    return dist[n];
}
int main() {
    cin>>n>>m;
    memset(h, -1, sizeof h);
    while (m--) {
        int a, b, c; cin>>a>>b>>c;
        add(a, b, c);
    }
    int ans = spfa();
    if (ans == -0x3f3f3f3f) puts("impossible");
    else cout<<ans;
}