[P4568飞行路线]

题目链接

[https://www.luogu.com.cn/problem/P4568]

思路

学会Dijkstra算法

参考代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, m, k;
    cin >> n >> m >> k;
    int s, t;
    cin >> s >> t;
    vector<vector<pair<int, int>>> g(n);
    for (int i = 0; i < m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq;
    vector<vector<int>> dist(n, vector<int>(k + 1, 0x3f3f3f3f));
    pq.push({0, s, 0});
    while (!pq.empty())
    {
        auto [d, u, t] = pq.top();
        pq.pop();
        if (d > dist[u][t])
        {
            continue;
        }
        for (auto [v, w] : g[u])
        {
            if (dist[v][t] > d + w)
            {
                dist[v][t] = d + w;
                pq.push({dist[v][t], v, t});
            }
            if (t < k && dist[v][t + 1] > d)
            {
                dist[v][t + 1] = d;
                pq.push({dist[v][t + 1], v, t + 1});
            }
        }
    }
    int ans = 0x3f3f3f3f;
    for (int i = 0; i <= k; i++)
    {
        ans = min(ans, dist[t][i]);
    }
    cout << ans << '\n';
    return 0;
}