Teleportation Solution
unknown
c_cpp
5 months ago
2.8 kB
10
Indexable
#include <bits/stdc++.h> using namespace std; //Credits: cw_42(Aviansh) void solve() { int n,m; cin >> n>> m; int a[n]; for(int &i : a) cin >> i; vector<pair<int,int>> g[n]; for(int i = 0; i < m;i++){ //add edges in our graph int a,b,d; cin >> a >> b >> d; g[a].push_back({b,d}); g[b].push_back({a,d}); } int k; cin >> k; while(k--){ //process all queries set<pair<int,array<int,2>>> pq; //{cost, {node, fuel}} int c,s,e; cin >> c >> s >> e; map<array<int,2>,int> vis; //map 1: vis[{node, fuel}]: min cost such that {cost, [node, fuel}} is visited & processed map<array<int,2>,int> he; //map 2: he[{node, fuel}]: min cost such that {cost, [node, fuel}} is visited pq.insert({0, {s , 0}}); //at src with 0 cost and 0 fuel int ans = -1; //impossible initally while(!pq.empty()) { pair<int,array<int,2>> p = *pq.begin(); pq.erase(pq.begin()); //take best option (greedy) if(vis.find(p.second) != vis.end()) continue; //we have come here before vis[p.second] = p.first; //we have come here now, processing if(p.second[0] == e){ //path found! ans = p.first; break; } for(pair<int,int> e : g[p.second[0]]) { //visit neighbours if(p.second[1] >= e.second){ //we can visit this edge with current fuel if(he.find({e.first,p.second[1] - e.second}) != he.end()) //this node has been visited if(he[{e.first,p.second[1] - e.second}] < p.first) //with lower cost? continue; //no use in visiting it now else //remove it from the set, we have found a better way! pq.erase({he[{e.first,p.second[1] - e.second}],{e.first,p.second[1] - e.second}}); pq.insert({p.first,{e.first,p.second[1] - e.second}}); //add the current path to set he[{e.first,p.second[1] - e.second}] = p.first; //its been visited! } } if(p.second[1] < c) { //refuel at current spot p.second[1]++; //1 unit fuel added p.first += a[p.second[0]]; //add to our cost pq.insert(p); //insert this state } } if(ans == -1) { //no path found cout << "impossible\n"; continue; } cout << ans << "\n"; //print answer } } signed main(){ ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--) solve(); return 0; }
Editor is loading...
Leave a Comment