关于spfa算法的一些见解（也是当时自己初学的一些疑惑解答）

话不多说，先上图

• 1号点入队，更新2号点和3号点的距离，并且2号点和3号点入队
• 3号点出队，更新4号点的距离，dist[4]=5,并且4号点入队
• 2号点出队更新4号点，dist[4]=4,
  注意：此时队列中在第二步时候4号点已经入队，并且没有出队，所以此时st[4]=true,所以此时只需要更新4号点的距
  离，没有必要再次入队，如果再次入队，则有两个距离相同的4号点，增加for循环的次数，多此一举；

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

using namespace std;

const int N = 100010;

int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
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()
{
    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 = h[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;
                }
            }
        }
    }

    return dist[n];
}

int main()
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);

    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    int t = spfa();

    if (t == 0x3f3f3f3f) puts("impossible");
    else printf("%d\n", t);

    return 0;
}