#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<long long int, long long int>;
const int inf = numeric_limits<int>::max();
const ll INF = numeric_limits<ll>::max();
const char sp = ' ';
const char nl = '\n';
/*
General Ideas
From Discord:
1) We can make use of the zeros by dijkstra'sing from H to any point that ends in zero.
2) Check which nodes are reachable from the source. Which is "legit" nodes we can use
Idea
1) DP+Dijkstra distance holding
K <- number of div/2s operations i used
why?
Div 2 cause dijkstra's to fail. Because values marked visited can actually have shorter paths if I visit a future node
and that has a div2 ability and go back to another I just was certain of finding the shortest path of.
So modifed dijkstras (d, node, k uses) and just dist[node] fails
First things:
Mark all nodes reachable from 0
Dijsktra's from H
dist[0][0] = 0.0
Check all distances to neighbouring stuff
for neighbor:
if(neighbor value == 1):
standard stuff
dist[neighbor][k] = min(dist[node][k] + weight(neighbor, node))
if(neighbor value == 0):
we found the shortest path
return this value
//pq ensures this is smallest
if(neighbor value == 2):
Choose to use it
if(k <= maximum_k_allowed){
dist[neighbour][k+1] = min(dist[neighbour][k+1],(dist[node][k] + weight(neighbor,node) / pow(2,k)));
}
dist[neighbour][k] = min(dist[neighbour][k],dist[node][k] + weight(neighbor,node));
Or Not
*/
void DFS(int H, int node, vector<bool> &reachable, vector<vector<pair<ll, long double> > > &Graph){
if(reachable[node] || node == H){
return;
} else {
reachable[node] = true;
for(auto &[neigh, weight]: Graph[node]){
if(!reachable[neigh]){
DFS(H, neigh, reachable, Graph);
}
}
return;
}
}
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
vector<vector<pair<ll, long double> > > Graph(N);
for(int i = 0; i < M; i++){
Graph[x[i]].push_back({y[i],(long double) c[i]});
Graph[y[i]].push_back({x[i],(long double) c[i]});
}
vector<bool> reachable(N,false);
DFS(H,0,reachable, Graph);
if(!reachable[H]){
return -1;
}
long double infi = 5e14;
vector<vector<long double> > distancedp(N,vector<long double>(K, infi));
priority_queue<tuple<long double, ll, ll>, vector<tuple<long double, ll, ll> >, greater<tuple<long double, ll, ll> > > pq;
pq.push({(long double)0, (ll) 0, H});
distancedp[H][0] = 0;
arr[0] = 0;
while(!pq.empty()){
auto [d, kcount, node] = pq.top(); pq.pop();
if(d > distancedp[node][kcount]){
continue;
}
if(arr[node] == 0){
return distancedp[node][kcount];
}
for(auto [neigh, weight]: Graph[node]){
if(neigh == H){
continue;
}
if(reachable[neigh]){
if(arr[neigh] == 2 && kcount < K){
if(distancedp[neigh][kcount + 1] > d + (long double)weight/ (pow((long double)2,(long double) kcount + 1))){
distancedp[neigh][kcount + 1] = d + (long double)weight/ (pow((long double)2,(long double) kcount + 1));
pq.push({distancedp[neigh][kcount + 1], kcount + 1, neigh});
}
}
//don't use powerup
if(distancedp[neigh][kcount] > d + (long double)weight/ (pow((long double)2,(long double) kcount))){
distancedp[neigh][kcount] = d + (long double)weight/ (pow((long double)2,(long double) kcount));
pq.push({distancedp[neigh][kcount],kcount, neigh});
}
}
}
}
return -1;
}
// int main() {
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// cout << solve(3, 2, 30, 2, {1, 2}, {2, 0}, {12, 4}, {1, 2, 1}) << nl;
// cout << solve(4, 4, 30, 3, {0, 0, 1, 2}, {1, 2, 3, 3}, {5, 4, 2, 4}, {1, 0, 2, 1}) << nl;
// }
