Submission #1183655

#TimeUsernameProblemLanguageResultExecution timeMemory
1183655meicrisToll (BOI17_toll)C++17
8 / 100
3111 ms537468 KiB
#include <bits/stdc++.h> using namespace std; const int INF = 1e9; int K, N, M, O; vector<vector<pair<int, int>>> graph; unordered_map<int, vector<int>> dist_cache; vector<int>& dijkstra(int s) { vector<int>& dist = dist_cache[s]; dist.assign(N, INF); dist[s] = 0; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq; pq.push({0, s}); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (d > dist[u]) continue; for (auto& [v, cost] : graph[u]) { if (dist[v] > d + cost) { dist[v] = d + cost; pq.push({dist[v], v}); } } } return dist; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> K >> N >> M >> O; graph.resize(N); for (int i = 0; i < M; ++i) { int a, b, t; cin >> a >> b >> t; if (b / K == (a / K) + 1) graph[a].emplace_back(b, t); } while (O--) { int a, b; cin >> a >> b; if (!dist_cache.count(a)) dist_cache[a].resize(N); vector<int>& d = dist_cache[a][0] ? dist_cache[a] : dijkstra(a); int res = d[b]; cout << (res == INF ? -1 : res) << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...