#include <bits/stdc++.h> using namespace std; // Use long long for everything to prevent overflow #define int long long // State: Cost, u, t1, t2, t3, t4, t5 (0 = Unused, 1 = Used) #define state tuple<int,int,int,int,int,int,int> const int INF = 1e18; int votecity[5005]; vector<pair<int,int>> mp[5005]; // Declare global to avoid stack overflow, reset it inside the loop int vsmp[5005][2][2][2][2][2]; int32_t main(){ cin.tie(NULL)->sync_with_stdio(false); int n, e, k; cin >> n >> e >> k; for(int i = 0; i < k; i++){ cin >> votecity[i]; } for(int i = 0; i < e; i++){ int a, b, c; cin >> a >> b >> c; mp[a].push_back({b, c}); } int q; cin >> q; while(q--){ int s, p1, p2, p3, p4, p5; cin >> s >> p1 >> p2 >> p3 >> p4 >> p5; // 1. Initialize 6D array to Infinity for(int i = 0; i < n; i++) for(int r1 = 0; r1 < 2; r1++) for(int r2 = 0; r2 < 2; r2++) for(int r3 = 0; r3 < 2; r3++) for(int r4 = 0; r4 < 2; r4++) for(int r5 = 0; r5 < 2; r5++) vsmp[i][r1][r2][r3][r4][r5] = INF; priority_queue<state, vector<state>, greater<state>> pq; // 2. Start State: Node s, Cost 0, All tickets '0' (Unused) vsmp[s][0][0][0][0][0] = 0; pq.push({0, s, 0, 0, 0, 0, 0}); while(!pq.empty()){ auto [cost, town, te1, te2, te3, te4, te5] = pq.top(); pq.pop(); if(cost > vsmp[town][te1][te2][te3][te4][te5]) continue; for(auto [netown, necost] : mp[town]){ // --- Option 1: Don't use any new ticket (Walk normally) --- if(cost + necost < vsmp[netown][te1][te2][te3][te4][te5]){ vsmp[netown][te1][te2][te3][te4][te5] = cost + necost; pq.push({vsmp[netown][te1][te2][te3][te4][te5], netown, te1, te2, te3, te4, te5}); } // --- Option 2: Use Ticket 1 (If available, unused, and exists) --- // Condition: Ticket 1 is Unused (te1 == 0) AND Price is not -1 if(te1 == 0 && p1 != -1){ // Cost = Current + (Road * 0.9) + Ticket Price P1 int new_cost = cost + (necost * 9 / 10) + p1; // Transition to state where te1 is Used (1) if(new_cost < vsmp[netown][1][te2][te3][te4][te5]){ vsmp[netown][1][te2][te3][te4][te5] = new_cost; pq.push({new_cost, netown, 1, te2, te3, te4, te5}); } } // --- Option 3: Use Ticket 2 --- if(te2 == 0 && p2 != -1){ int new_cost = cost + (necost * 8 / 10) + p2; if(new_cost < vsmp[netown][te1][1][te3][te4][te5]){ vsmp[netown][te1][1][te3][te4][te5] = new_cost; pq.push({new_cost, netown, te1, 1, te3, te4, te5}); } } // --- Option 4: Use Ticket 3 --- if(te3 == 0 && p3 != -1){ int new_cost = cost + (necost * 7 / 10) + p3; if(new_cost < vsmp[netown][te1][te2][1][te4][te5]){ vsmp[netown][te1][te2][1][te4][te5] = new_cost; pq.push({new_cost, netown, te1, te2, 1, te4, te5}); } } // --- Option 5: Use Ticket 4 --- if(te4 == 0 && p4 != -1){ int new_cost = cost + (necost * 6 / 10) + p4; if(new_cost < vsmp[netown][te1][te2][te3][1][te5]){ vsmp[netown][te1][te2][te3][1][te5] = new_cost; pq.push({new_cost, netown, te1, te2, te3, 1, te5}); } } // --- Option 6: Use Ticket 5 --- if(te5 == 0 && p5 != -1){ int new_cost = cost + (necost * 5 / 10) + p5; if(new_cost < vsmp[netown][te1][te2][te3][te4][1]){ vsmp[netown][te1][te2][te3][te4][1] = new_cost; pq.push({new_cost, netown, te1, te2, te3, te4, 1}); } } } } // 3. Find the minimum cost to any voting city int final_ans = INF; for(int i = 0; i < k; i++){ for(int r1 = 0; r1 < 2; r1++) for(int r2 = 0; r2 < 2; r2++) for(int r3 = 0; r3 < 2; r3++) for(int r4 = 0; r4 < 2; r4++) for(int r5 = 0; r5 < 2; r5++) final_ans = min(final_ans, vsmp[votecity[i]][r1][r2][r3][r4][r5]); } if(final_ans == INF) cout << "-1\n"; else cout << final_ans << "\n"; } }