Bellman–Ford 算法是一种基于松弛（relax）操作的最短路算法，可以求出有负权的图的最短路，并可以对最短路不存在的情况进行判断。

有边数限制的最短路

普通做法

int ne[N], h[N], idx, e[N], wt[N]; // wt[]表示边权

void add(int u, int v, int w) // 链式前向星存图
{
    idx++;
    e[idx] = v;
    wt[idx] = w; // 边权
    ne[idx] = h[u];
    h[u] = idx;
}

int n, m, k;

int b[N];
int d[N];

int bellman_ford(int s)
{

    for (int i = 1; i <= n; i++)
    {
        d[i] = INF;
    }
    d[s] = 0;
    while (k--)
    {
        for (int i = 1; i <= n; i++)
        {
            b[i] = d[i];
        } // 新的一轮优化之前，把d给b
        for (int u = 1; u <= n; u++)
        {
            if (b[u] == INF)
            {
                continue;
            }
            for (int j = h[u]; j; j = ne[j])
            {
                int v = e[j];
                int w = wt[j];
                if (d[v] > b[u] + w)
                {
                    d[v] = b[u] + w;
                }
            }
        }
    }
    return d[n];
}

signed main()
{
    fst;
    n = read(), m = read(), k = read();
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        u = read();
        v = read();
        w = read();
        add(u, v, w);
    }
    int res = bellman_ford(1);
    if (res == INF)
    {
        cout << "impossible" << endl;
        return 0;
    }
    cout << res << endl;
    return 0;
}

堆优化

int n, m, s;

struct vnode
{
    int d;  // 点
    int wt; // 距离
};
vector<vnode> g[N];

bool vis[N];
int d[N];

void spfa(int s)
{
    queue<int> q;
    for (int i = 1; i <= n; i++)
    {
        d[i] = INF;
    }
    d[s] = 0;
    q.push(s);
    vis[s] = 1;
    while (!q.empty())
    {
        // 当队列非空
        // 我们应该去松弛
        int u = q.front();
        q.pop();
        vis[u] = 0;
        // 只要无法在松弛，就找到了最短路
        for (auto e : g[u])
        {
            int v = e.d;
            int w = e.wt;
            if (d[v] > d[u] + w)
            {
                d[v] = d[u] + w;
                if (vis[v] == 0)
                {
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
}
signed main()
{
    fst;

    n = read(), m = read(), s = read();
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        u = read();
        v = read();
        w = read();
        g[u].pb({v, w});
    }
    spfa(s);
    for (int i = 1; i <= n; i++)
    {
        cout << d[i] << " ";
    }
    cout << endl;
    return 0;
}