那用SPFA算法实现

同样是求解最短路问题，SPFA 算法是一种基于 Bellman-Ford 算法的优化，它可以处理负权边，但是在存在负环的情况下会出现无限循环的问题。下面是使用 SPFA 算法实现的代码：

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

using namespace std;

const int N = 1e6 + 10;

int n, m, s, t;
int h[N], e[N], ne[N], w[N], idx;
int dist[N];
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}

bool spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[s] = 0;

    queue<int> q;
    q.push(s);
    st[s] = true;

    while (!q.empty())
    {
        int t = q.front();
        q.pop();
        st[t] = false;

        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i], d = dist[t] + w[i];
            if (dist[j] > d)
            {
                dist[j] = d;
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return dist[t] < 0x3f3f3f3f;
}

int main()
{
    cin >> n >> m >> s >> t;

    memset(h, -1, sizeof h);
    while (m --)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }

    if (!spfa()) puts("impossible");
    else cout << dist[t] << endl;

    return 0;
}

时间复杂度方面，SPFA 算法的时间复杂度取决于队列中元素的个数，最坏情况下时间复杂度可以达到 O(nm)，但是实际上大多数情况下它的时间复杂度是比较优秀的。