#include "cyberland.h"
#include <vector>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <utility>
#define v vector
#define s set
#define u_s unordered_set
#define u_m unordered_map
#define q queue
#define p_q priority_queue
#define p pair
#define ll long long
using namespace std;
class WorldMap {
const int maxShift = 66;
const ll tempInf = 1000000000000000;
int countryCount; int cyberland; double minimum;
u_m<int, v<p<int, int>>> friends;
v<ll> dspaSourceResult;
u_m<int, ll> halvers;
u_m<int, v<p<double, int>>> halverQueues;
v<u_m<int, double>> halverVisits;
u_s<int> checkedHalvers;
v<int> powers;
public:
// Initialize the world map
WorldMap(int countries, int destinationIndex) {
countryCount = countries;
cyberland = destinationIndex;
minimum = tempInf;
friends.clear(); dspaSourceResult.clear();
halvers.clear(); halverQueues.clear(); checkedHalvers.clear(); halverVisits.clear();
powers.clear();
}
void connect(int friend1, int friend2, int distance) {
friends[friend1].push_back(make_pair(friend2, distance));
friends[friend2].push_back(make_pair(friend1, distance));
}
void notePowers(v<int> arr) {
powers = arr;
}
void dspaSource() {
// Initialize stuff
dspaSourceResult.clear(); dspaSourceResult.resize(countryCount, tempInf);
p_q<p<ll, int>, v<p<ll, int>>, greater<p<ll, int>>> dspaQueue;
dspaQueue.push(make_pair(0, 0));
dspaSourceResult[0] = 0;
int selected; int friendID; int friendDist;
// Go through the queue
while (!(dspaQueue.empty())) {
selected = dspaQueue.top().second; dspaQueue.pop();
// Go through the first-in-line's friends
for (p<int, int> fren : friends[selected]) {
friendID = fren.first; friendDist = fren.second;
// If the friend has 0-powers
if (powers[friendID] == 0) {
// Propagate only if it hasn't been hit before
if (dspaSourceResult[friendID] > 0) {
dspaSourceResult[friendID] = 0;
// Note that we cannot leave Cyberland
if (friendID != cyberland) dspaQueue.push(make_pair(0, friendID));
}
} else {
// Propagate only if the value changes
if (dspaSourceResult[selected] + friendDist < dspaSourceResult[friendID]) {
dspaSourceResult[friendID] = dspaSourceResult[selected] + friendDist;
// Note that we cannot leave Cyberland
if (friendID != cyberland) dspaQueue.push(make_pair(dspaSourceResult[friendID], friendID));
}
}
}
}
}
void dspaDestination() {
// Initialize stuff
v<ll> dspaDestinationResult(countryCount, tempInf);
p_q<p<ll, int>, v<p<ll, int>>, greater<p<ll, int>>> dspaQueue;
u_s<int> halverSet;
dspaQueue.push(make_pair(0, cyberland));
dspaDestinationResult[cyberland] = 0;
int selected; int friendID; int friendDist;
// Go through the queue
while (!(dspaQueue.empty())) {
selected = dspaQueue.top().second; dspaQueue.pop();
// Go through the first-in-line's friends
for (p<int, int> fren : friends[selected]) {
friendID = fren.first; friendDist = fren.second;
// Propagate only if the value changes
if (dspaDestinationResult[selected] + friendDist < dspaDestinationResult[friendID]) {
dspaDestinationResult[friendID] = dspaDestinationResult[selected] + friendDist;
// Log if friend's power is 2
dspaQueue.push(make_pair(dspaDestinationResult[friendID], friendID));
if (powers[friendID] == 2) halverSet.insert(friendID);
}
}
}
// Deal with the queue for 2-powers
for (auto selected: halverSet) halvers[selected] = dspaDestinationResult[selected];
}
double div2(double ans, int expo) {
double k = 2;
while (expo != 0) {
if (expo & 1) ans = ans / k;
expo = expo >> 1; k = k * k;
}
return ans;
}
bool navigate(int halverInd, double currDistance, double lastDistance, int halvesUsed, int maxHalves) {
// Navigating from Cyberland back to home; first update
double newDist = currDistance + lastDistance;
minimum = min(minimum, newDist + div2(dspaSourceResult[halverInd], halvesUsed));
// Then try to minimize saved path length
if ((halvesUsed < maxHalves) && (newDist < minimum - max(minimum * 1.0E-6, 1.0E-6))) {
double barrier = (halverVisits[halvesUsed][halverInd] == 0) ? tempInf : halverVisits[halvesUsed][halverInd];
if (!(newDist <= barrier - max(barrier * 1.0E-6, 1.0E-6))) return false;
halverVisits[halvesUsed][halverInd] = newDist;
minimum = min(minimum, newDist + div2(dspaSourceResult[halverInd], halvesUsed + 1));
// If maxHalves has not been reached, go through each friend
// Initialize stuff
if (checkedHalvers.find(halverInd) == checkedHalvers.end()) {
v<double> dspaCustomResult(countryCount, tempInf);
p_q<p<double, int>, v<p<double, int>>, greater<p<double, int>>> dspaQueue;
v<p<double, int>> dspaQueueCopy;
dspaQueue.push(make_pair(0, halverInd));
dspaCustomResult[halverInd] = 0;
int selected; double selectedDist; int friendID; double friendDist; bool selfSatisfaction = false;
// Go through the queue
while (!(dspaQueue.empty())) {
selected = dspaQueue.top().second; selectedDist = dspaQueue.top().first; dspaQueue.pop();
// Iterate to next loop
if (powers[selected] == 2) {
if (dspaSourceResult[selected] != tempInf) {
if ((selectedDist != 0) && (selectedDist != tempInf)) {
dspaQueueCopy.push_back(make_pair(selectedDist, selected));
bool get = navigate(selected, newDist, div2(selectedDist, halvesUsed + 1), halvesUsed + 1, maxHalves);
if (get) break;
}
}
if ((selected == halverInd) && (selectedDist != 0)) continue;
}
// Go through the first-in-line's friends
for (p<int, int> fren : friends[selected]) {
friendID = fren.first; friendDist = fren.second;
// Propagate only if the value changes
if (dspaCustomResult[selected] + friendDist < dspaCustomResult[friendID]) {
dspaCustomResult[friendID] = dspaCustomResult[selected] + friendDist;
// Note that we cannot leave Cyberland
if (friendID != cyberland) dspaQueue.push(make_pair(dspaCustomResult[friendID], friendID));
} else if ((!(selfSatisfaction)) && (friendID == halverInd)) {
// If it loops to itself, return that as well
dspaQueue.push(make_pair(dspaCustomResult[selected] + friendDist, halverInd));
selfSatisfaction = true;
}
}
}
halverQueues[halverInd] = dspaQueueCopy;
checkedHalvers.insert(halverInd);
} else {
for (p<double, int> top : halverQueues[halverInd]) {
bool get = navigate(top.second, newDist, div2(top.first, halvesUsed + 1), halvesUsed + 1, maxHalves);
if (get) break;
}
}
return false;
} else return true;
}
double determinePath(int twoPower) {
// Perform DijkstraSPA once from source, apply 0 and 1 rules
dspaSource();
// Perform DijkstraSPA once from destination, record 2s
dspaDestination();
// Then consolidate hereon
if (dspaSourceResult[cyberland] == tempInf) return -1;
// If Cyberland is reachable
p_q<p<ll, int>, v<p<ll, int>>, greater<p<ll, int>>> dfsFromDestinationQueue;
minimum = dspaSourceResult[cyberland];
for (auto info : halvers) dfsFromDestinationQueue.push(make_pair(info.second, info.first));
twoPower = min(twoPower, maxShift);
halverVisits.resize(twoPower + 1);
// Go through each 2-power starting from destination, dfs-style
p<ll, int> currentHalver;
while (!(dfsFromDestinationQueue.empty())) {
currentHalver = dfsFromDestinationQueue.top(); dfsFromDestinationQueue.pop();
if ((currentHalver.first != tempInf) && (dspaSourceResult[currentHalver.second] != tempInf)) {
bool get = navigate(currentHalver.second, 0, currentHalver.first, 0, twoPower);
if (get) break;
}
}
return minimum;
}
};
double solve(int N, int M, int K, int H, v<int> x, v<int> y, v<int> c, v<int> arr) {
// Rename every int to something more descriptive
int countryCount = N; int roadCount = M; int bitShifter = K; int cyberLocation = H;
WorldMap theRoadToCyberland(countryCount, cyberLocation);
for (int road = 0; road < roadCount; road++)
theRoadToCyberland.connect(x[road], y[road], c[road]);
theRoadToCyberland.notePowers(arr);
return theRoadToCyberland.determinePath(bitShifter);
}
