#include <bits/stdc++.h>
#include "prettyprint.h"
#define int int64_t
using namespace std;
vector<map<int, int, greater<int>>> graph; // map<target, distance>
int K;
const int INF = 1e10;
//vector<pair<int, int>> distance; // pair<start, distance>
int findShortestDistance(int s, int e) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
unordered_map<int, int> distance;
pq.emplace(0, s);
while (!pq.empty()){
auto [cost, pos] = pq.top();
pq.pop();
if (distance.find(pos) != distance.end()) continue;
distance[pos] = cost;
int k = 0;
for (const auto& [p, c] : graph[pos]) {
if (p <= e) { // can't go backwards due to graph structure
pq.emplace(cost + c, p);
if (++k >= K) break;
}
}
}
return distance.find(e) == distance.end() ? INF : distance.at(e);
}
void addSkipEdges(int skipDistance) {
for (int startCluster = 0; startCluster < graph.size() / K; startCluster+=skipDistance) {
for (int startNode = startCluster * K; startNode < (startCluster + 1) * K; startNode++) {
for (int endNode = (startCluster + 1) * K; endNode < (startCluster + 2) * K; endNode++) {
if (endNode > graph.size()) break;
graph[startNode][endNode] = findShortestDistance(startNode, endNode);
}
}
}
}
main() {
int N,M,O;
cin >> K >> N >> M >> O;
graph.resize(N);
for (int i = 0; i < M; i++) {
int s, e, c;
cin >> s >> e >> c;
graph[s][e] = c;
}
for (int skipDist = 2; skipDist < N / K; skipDist *= 2) {
addSkipEdges(skipDist);
}
for (int o = 0; o < O; o++) {
int s, e;
cin >> s >> e;
int dist = findShortestDistance(s, e);
cout << (dist < INF ? dist : -1) << "\n";
}
}
Compilation message
toll.cpp:2:10: fatal error: prettyprint.h: No such file or directory
2 | #include "prettyprint.h"
| ^~~~~~~~~~~~~~~
compilation terminated.
