Flight Routes

Your task is to find the k shortest flight routes from Syrjälä to Metsälä. A route can visit the same city several times.

Note that there can be several routes with the same price and each of them should be considered.

Example:

Input: n = 4, m = 6, k = 3, arr = {{1, 2, 1}, {1, 3, 3}, {2, 3, 2}, {2, 4, 6}, {3, 2, 8}, {3, 4, 1}}
Output: 4 4 7

Approach

C++

#include <bits/stdc++.h>
using namespace std;

void flightRoutes(long long n, long long m, long long k,
                  vector<vector<long long>> &arr)
{
    vector<pair<long long, long long>> adj[n + 1];
    for (long long i = 0; i < m; i++)
    {
        long long a = arr[i][0], b = arr[i][1];
        long long w = arr[i][2];

        adj[a].push_back({b, w});
    }
    priority_queue<pair<long long, long long>> q;
    q.push({0, 1});
    long long vis[n + 1] = {0};
    while (!q.empty() && vis[n] < k)
    {
        long long a = q.top().second;
        long long d = q.top().first;
        q.pop();
        vis[a]++;
        if (a == n)
            cout << -d << " ";
        if (vis[a] <= k)
        {
            for (auto [b, w] : adj[a])
            {

                q.push({d - w, b});
            }
        }
    }
}
int main()
{
    long long n = 4, m = 6, k = 3;

    vector<vector<long long>> arr = {{1, 2, 1},
                                     {1, 3, 3},
                                     {2, 3, 2},
                                     {2, 4, 6},
                                     {3, 2, 8},
                                     {3, 4, 1}};

    flightRoutes(n, m, k, arr);

    return 0;
}