LightOJ - New Traffic System

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

const int maxN = 10100;
vector<pair<pair<int,int>,int>> adj[maxN];
int cost[maxN];

void dijkstra (int source,int n,int d) {
    for (int i = 0; i <= n; ++i) cost[i] = (int) 1e7;
    cost[source] = 0;
    priority_queue<pair<pair<int,int>,int>> pq;
    pq.push(make_pair(make_pair(0,0),0));
    while (!pq.empty()) {
        int node = pq.top().second;
        int used = abs(pq.top().first.first);
        int dist = abs(pq.top().first.second);
        pq.pop();
        for (pair<pair<int,int>,int> child : adj[node]) {
            int child_cost = child.first.second;
            int child_node = child.first.first;
            int child_used = child.second;
            if (child_used + used <= d and child_cost + dist < cost[child_node]) {
                cost[child_node] = child_cost + dist;
                pq.push(make_pair(make_pair(-(child_used + used),-cost[child_node]),child_node));
            }
        }
    }
}

int main () {
     ios::sync_with_stdio(false);
     cin.tie(nullptr);
     cout.tie(nullptr);
     int T;
     cin >> T;
     for (int test_case = 1; test_case <= T; ++test_case) {
         int n,m,k,d;
         cin >> n >> m >> k >> d;
         for (int i = 0; i <= n; ++i) adj[i].clear();
         for (int i = 1; i <= m; ++i) {
             int u,v,cost;
             cin >> u >> v >> cost;
             adj[u].push_back(make_pair(make_pair(v,cost),0));
         }
         for (int i = 1; i <= k; ++i) {
             int u,v,cost;
             cin >> u >> v >> cost;
             adj[u].push_back(make_pair(make_pair(v,cost),1));
         }
         dijkstra(0,n,d);
         cout << "Case " << test_case << ": " << (cost[n - 1] >= (int) 1e7 ? "Impossible" : to_string(cost[n - 1])) << '\n';
     }
     //cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
}