【題解】CSES 1196 Flight Routes

【題目敘述】https://cses.fi/problemset/task/1196/

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
 
int n, m, k, a, b, c;
vector <long long> ans[100005];
vector <pair <int, int> > v[100005];
 
int main() {
    cin >> n >> m >> k;
    for (int i = 0; i < m; i++){
        cin >> a >> b >> c;
        v[a].push_back({b, c});
    }
    priority_queue <pair <long long, int>, vector<pair<long long, int> >, greater<pair<long long, int> > > pq;
    pq.push({0, 1});
    while (!pq.empty()){
        auto now = pq.top();
        pq.pop();
        if (ans[now.second].size() == k) continue;
        ans[now.second].push_back(now.first);
        for (auto i:v[now.second]){
            pq.push({now.first + i.second, i.first});
        }
    }
    for (int i = 0; i < k; i++){
        cout << ans[n][i] << " ";
    }
}
分享本文 Share with friends