$$ Floyd : O(N^3)|适用带负权|跑两次可判负环 $$
$$ Dijkstra : 朴素:O(N^2) |堆优化:O(Mlog_2N)|不适用带负权|不可判负环 $$
$$ Bellman-Ford :O(NM) $$
$$ Spfa : 一般:O(M)|最坏:O(NM)|适用带负权|可以判负环 $$

总结：

如果没有负权,最好用堆优化的Dijkstra

如果存在则考虑Spfa,数据小的时候可以考虑Floyd

板子

Floyd

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

using namespace std;

const int N = 110;

int n, m;
int f[N][N];

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

    memset(f, 0x3f, sizeof f);
    while (m --)
    {
        int a, b, c;
        scanf ("%d %d %d", &a, &b, &c);
        f[a][b] = f[b][a] = min(c, f[a][b]);
    }

    for (int k = 1; k <= n; k ++)
        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= n; j ++)
                if (i == j) f[i][j] = 0;
                else f[i][j] = min(f[i][j], f[i][k] + f[k][j]);

    for (int i = 1; i <= n; i ++)
    {
        for (int j = 1; j <= n; j ++)
            printf ("%d ", f[i][j]);
        puts("");
    }

    return 0;
}

朴素Dijkstra

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

using namespace std;

const int N = 510;

int n, m;
int g[N][N], dis[N];
bool st[N];

int Dijkstra()
{
    memset(dis, 0x3f, sizeof dis);
    dis[1] = 0;

    for (int i = 0; i < n - 1; i ++) // 要找n - 1次点（即将除1外的点依次加入到集合S中）
    {
        int t = -1;
        for (int j = 1; j <= n; j ++)
            if (!st[j] && (t == -1 || dis[t] > dis[j])) t = j; // 首先j要不在集合S中，然后要保证j是到节点1距离最小的点
        st[t] = true; // 标记t已经进入S集合了

        for (int j = 1; j <= n; j ++)  // 用t点去松弛其他点到节点1的距离
            dis[j] = min(dis[j], dis[t] + g[t][j]);
    }

    return dis[n] == 0x3f3f3f3f ? -1 : dis[n];
}

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

    memset(g, 0x3f, sizeof g);
    while (m --)
    {
        int a, b, c;
        scanf ("%d %d %d", &a, &b, &c);
        g[a][b] = min(g[a][b], c); // 避免重边的影响
    }

    printf ("%d", Dijkstra());
    return 0;
}

堆优化Dijkstra

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

using namespace std;

typedef pair<int, int> PII;

const int N = 150050;

int n, m;
int h[N], e[N], w[N], ne[N], idx;
int dis[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 Dijkstra()
{
    memset(dis, 0x3f, sizeof dis);
    priority_queue<PII, vector<PII>, greater<PII>> heap; // 创建一个小根堆

    dis[1] = 0;
    heap.push({0, 1}); // first为距离，second为节点编号

    while (heap.size())
    {
        auto t = heap.top(); // 取距离节点1最小的点
        heap.pop();

        int d = t.first, ver = t.second;
        if (st[ver]) continue; // 每一个点第一次遍历时一定是最小距离，不需要遍历第二次
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (d + w[i] < dis[j]) // 如果可以松弛
            {
                dis[j] = d + w[i];
                heap.push({dis[j], j});
            }
        }
    }

    return dis[n] == 0x3f3f3f3f ? -1 : dis[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);
    }

    printf ("%d", Dijkstra());
    return 0;
}

Bellman_Ford

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

using namespace std;

const int N = 10010;

int n, m, k;
int dis[N], last[N];

struct edge
{
    int a, b, w;
}e[N];

void Bellman_Ford()
{
    memset(dis, 0x3f, sizeof dis);
    dis[1] = 0;

    for (int i = 0; i < k; i ++) // 要经过k次松弛，即经过k条边
    {
        memcpy(last, dis, sizeof dis); // 每一次都要记录一下上一次松弛后的结果，以免发生串联更新导致结果不是经历过k条边后的结果
        for (int j = 1; j <= m; j ++)
        {
            int a = e[j].a, b = e[j].b, w = e[j].w;

            dis[b] = min(dis[b], last[a] + w);
        }
    }

    if (dis[n] > 0x3f3f3f3f / 2) puts("impossible");
    else printf ("%d", dis[n]);
}

int main()
{
    scanf ("%d %d %d", &n, &m, &k);
    for (int i = 1; i <= m; i ++)
    {
        int a, b, w;
        scanf ("%d %d %d", &a, &b, &w);
        e[i] = {a, b, w};
    }

    Bellman_Ford();

    return 0;
}

SPFA

// 求最短路
void SPFA()
{
    queue<int> q;
    q.push(1);
    st[1] = true; // true表示已经在队列中

    memset(dis, 0x3f, sizeof dis);
    dis[1] = 0;

    while (!q.empty())
    {
        int t = q.front();
        q.pop();
        st[t] = false; // 出队列就标记为false

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dis[j] > dis[t] + w[i]) // 如果可以松弛
            {
                dis[j] = dis[t] + w[i];
                if (!st[j]) // 如果j不在队列中
                {
                    st[j] = true;
                    q.push(j);
                }
            }
        }
    }

    if (dis[n] == 0x3f3f3f3f) puts("impossible");
    else printf ("%d", dis[n]);
}
// 判负环
bool SPFA()
{
    queue<int> q;
    for (int i = 1; i <= n; i ++) // 要把所有的点先放入队列中
    {
        st[i] = true;
        q.push(i);
    }

    while (!q.empty())
    {
        int t = q.front();
        q.pop();
        st[t] = false; // 出队列就标记为false

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dis[j] > dis[t] + w[i]) // 如果可以松弛
            {
                dis[j] = dis[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n) return true; // 如果经过了n条边，那一定经过了n+1个点，则一定纯在负环
                if (!st[j]) // 如果j不在队列中
                {
                    st[j] = true;
                    q.push(j);
                }
            }
        }
    }

    return false;
}

昂贵的聘礼

思路: 对于每个物品, 从它的所有替代品往它连一条边, 边权为优惠价格, 再建一个虚拟点(代表直接买这个物品的方案)

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

using namespace std;

const int N = 110, INF = 0x3f3f3f3f;

int m, n;
int l[N], p[N];
int g[N][N], dis[N];
bool st[N];

int Dijkstra(int a, int b)
{
    memset(dis, 0x3f, sizeof dis);
    memset(st, 0, sizeof st);
    dis[0] = 0;

    for (int i = 1; i <= n + 1; i ++)
    {
        int t = -1;
        for (int j = 0; j <= n; j ++) // 这里一定要从0开始, 让0号节点先到集合当中
            if (!st[j] && (t == -1 || dis[j] < dis[t]))
                t = j;

        st[t] = true;

        for (int j = 1; j <= n; j ++)
            if (a <= l[j] && l[j] <= b) // 要等级在允许的范围内即可
                dis[j] = min(dis[j], dis[t] + g[t][j]);
    }

    return dis[1];
}

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

    memset(g, 0x3f, sizeof g);

    for (int i = 1; i <= n; i ++) g[i][i] = 0;

    for (int i = 1; i <= n; i ++)
    {
        int cnt;
        cin >> p[i] >> l[i] >> cnt;
        g[0][i] = p[i]; // 这是直接买的价格
        while (cnt --)
        {
            int id, v;
            cin >> id >> v;
            g[id][i] = v;
        }
    }

    int res = INF;
    // 在酋长允许的等级范围内都跑一遍最短路
    for (int i = l[1] - m; i <= l[1]; i ++) res = min(res, Dijkstra(i, i + m));

    cout << res;
    return 0;
}