cheapest_parking_slot.cpp

/*
There is a parking facility which is in the form of a graph having N nodes and M edges. The graph
does not have self loops or multiple edges.
Each node represents a parking slot and has a capacity of vehicles it can hold. Each edge
has a weight w representing we can reach from node u to node v incurring a cost of w units. All
parking slots have a parking fee F per vehicle which is same for all slots. There are K identical
vehicles entering the parking facility, each vehicle enumerated with a distinct number from 1 to K.
The vehicles enter in their natural order, that is, vehicle number 1 enters, then vehicle number 2,
then 3 and so on till vehicle number K.
For each vehicle, you have to print the minimum total cost that is incurred on the vehicle owner.
Here, total cost includes cost of the path taken to reach the parking slot and parking fee of the
slot.
It is guaranteed that you can reach any slot from any other slot.
All vehicles entering the parking facility enter from the parking slot 1.
Input Format:
The first line consists of three integers N, M and F, denoting number of nodes, number of edges and
parking fee respectively.
The second line consists of N space separated integers denoting the parking capacity of each
parking slot. This array is represented by C[].
Following M lines contain three space separated integers each:
and w, denoting we can reach from node u to node v incurring a cost of w units.
The last line of input contains an integer K.
Output Format:
Print K space separated integers denoting answer for each vehicle.
integer in the space separated integers denotes answer for vehicle number.
If it is not possible to park a vehicle , print for that vehicle.

*/

#include <map>
#include <vector>
#include <utility>
#include <queue>
#include <set>
#include <iostream>
#include <algorithm>
#include <climits>

std::vector<std::vector<std::pair<double, double>>> adj;
std::vector<long long> d, c;


void dijktras(long long s)
{
    d[s] = 0;
    std::priority_queue<std::pair<double, double>, std::vector<std::pair<double, double>>,
                        std::greater<std::pair<double, double>>> pq;

    pq.push({0, s});
    while (!pq.empty())
    {
        long long v = pq.top().second;
        long long d_v = pq.top().first;
        pq.pop();
        if (d[v] != d_v)
            continue;
        for (auto &edge : adj[v])
        {
            long long len = edge.second;
            long long to = edge.first;
            if (d[to] > d[v] + len)
            {
                d[to] = d[v] + len;
                pq.push({d[to], to});
            }
        }
    }
}
int main()
{
    long long n, m, f;
    std::cin >> n >> m >> f;
    adj.resize(n + 1);
    d.assign(n + 1, LONG_LONG_MAX);
    c.resize(n + 1);
    for (size_t i = 1; i <= n; i++)
        std::cin >> c[i];
    while (m--)
    {
        long long u, v, w;
        std::cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    long long k;
    std::cin >> k;
    dijktras(1);
    std::multiset<long long> ml;
    std::vector<std::pair<long long, long long>> v;
    for (size_t i = 1; i <= n; i++)
        v.push_back({d[i], i});
    std::sort(v.begin(), v.end());
    for (size_t i = 0; i < v.size(); i++)
    {
        int u = v[i].second;
        for (int j = 0; j < c[u]; j++)
        {
            ml.insert(v[i].first);
            if (ml.size() == k)
                break;
        }
        if (ml.size() == k)
            break;
    }
    for (auto &u : ml)
        std::cout << u + f << " ";
    if (k > ml.size())
        for (size_t i = 0; i < k - ml.size(); i++)
            std::cout << -1 << " ";
    return EXIT_SUCCESS;
}