拆点、二维点、pair 套 pair

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10000;
const int INF = 2147483647;
int n, m, k;
int s, t;
vector<pair<int, int>> e[MAXN + 5];
// dis[i][j] 走到 i 号点，用了 j 次免费的最小花费
int dis[MAXN + 5][15];
bool vis[MAXN + 5][15];
// <dis, <i号点,j次免费>>
priority_queue<pair<int, pair<int, int>>> pq;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> k;
    cin >> s >> t;
    s++, t++;
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        u++, v++;
        e[u].push_back({v, w});
        e[v].push_back({u, w});
    }
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= k; j++)
        {
            dis[i][j] = INF;
            vis[i][j] = false;
        }
    dis[s][0] = 0;
    pq.push({-0, {s, 0}});
    while (!pq.empty())
    {
        int u = pq.top().second.first;
        int uu = pq.top().second.second;
        pq.pop();
        if(vis[u][uu])
            continue;
        vis[u][uu] = true;
        for (int i = 0; i < e[u].size(); i++)
        {
            int v = e[u][i].first;
            int w = e[u][i].second;
            // 不花费额外免费次数
            if (dis[u][uu] + w < dis[v][uu])
            {
                dis[v][uu] = dis[u][uu] + w;
                pq.push({-dis[v][uu], {v, uu}});
            }
            // 这趟免费
            if (uu < k && dis[u][uu] < dis[v][uu + 1])
            {
                dis[v][uu + 1] = dis[u][uu];
                pq.push({-dis[v][uu + 1], {v, uu + 1}});
            }
        }
    }
    int ans = dis[t][0];
    for (int i = 1; i <= k; i++)
        ans = min(ans, dis[t][i]);
    cout << ans;
    return 0;
}

拆点、二维点、结构体

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10000;
const int INF = 2147483647;
int n, m, k;
int s, t;
vector<pair<int, int>> e[MAXN + 5];
// dis[i][j] 走到 i 号点，用了 j 次免费的最小花费
int dis[MAXN + 5][15];
bool vis[MAXN + 5][15];
// dij
struct Point
{
    // 距离、点的编号、免费次数
    int dis, idx, cnt;
};
bool operator<(const Point &a, const Point &b)
{
    return a.dis > b.dis;
}
priority_queue<Point> pq;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> k;
    cin >> s >> t;
    s++, t++;
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        u++, v++;
        e[u].push_back({v, w});
        e[v].push_back({u, w});
    }
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= k; j++)
        {
            dis[i][j] = INF;
            vis[i][j] = false;
        }
    dis[s][0] = 0;
    pq.push({0, s, 0});
    while (!pq.empty())
    {
        int u = pq.top().idx;
        int uu = pq.top().cnt;
        pq.pop();
        if(vis[u][uu])
            continue;
        vis[u][uu] = true;
        for (int i = 0; i < e[u].size(); i++)
        {
            int v = e[u][i].first;
            int w = e[u][i].second;
            // 不花费额外免费次数
            if (dis[u][uu] + w < dis[v][uu])
            {
                dis[v][uu] = dis[u][uu] + w;
                pq.push({dis[v][uu], v, uu});
            }
            // 这趟免费
            if (uu < k && dis[u][uu] < dis[v][uu + 1])
            {
                dis[v][uu + 1] = dis[u][uu];
                pq.push({dis[v][uu + 1], v, uu + 1});
            }
        }
    }
    int ans = dis[t][0];
    for (int i = 1; i <= k; i++)
        ans = min(ans, dis[t][i]);
    cout << ans;
    return 0;
}

拆点、真的建出来新的点和边

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10000;
const int INF = 2147483647;
int n, m, k;
int s, t;
int tot, idx[MAXN + 5][15]; // idx[i][j] i号点j次免费时的抽象点
vector<pair<int, int>> e[MAXN * 11 + 5];
// dis[i][j] 走到 i 号点，用了 j 次免费的最小花费
int dis[MAXN * 11 + 5];
bool vis[MAXN * 11 + 5];
// dij
priority_queue<pair<int, int>> pq;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= k; j++)
            idx[i][j] = ++tot;
    cin >> s >> t;
    s++, t++;
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        u++, v++;
        for (int j = 0; j <= k; j++)
        {
            e[idx[u][j]].push_back({idx[v][j], w});
            e[idx[v][j]].push_back({idx[u][j], w});
            if (j < k)
            {
                e[idx[u][j]].push_back({idx[v][j + 1], 0});
                e[idx[v][j]].push_back({idx[u][j + 1], 0});
            }
        }
    }
    for (int i = 1; i <= tot; i++)
        dis[i] = INF;
    dis[idx[s][0]] = 0;
    pq.push({-0, idx[s][0]});
    while (!pq.empty())
    {
        int u = pq.top().second;
        pq.pop();
        if(vis[u])
            continue;
        vis[u] = true;
        for (int i = 0; i < e[u].size(); i++)
        {
            int v = e[u][i].first;
            int w = e[u][i].second;
            // 不花费额外免费次数
            if (dis[u] + w < dis[v])
            {
                dis[v] = dis[u] + w;
                pq.push({-dis[v], v});
            }
        }
    }
    int ans = dis[idx[t][0]];
    for (int i = 1; i <= k; i++)
        ans = min(ans, dis[idx[t][i]]);
    cout << ans;
    return 0;
}