Submission #1183672

#TimeUsernameProblemLanguageResultExecution timeMemory
1183672meicrisToll (BOI17_toll)C++17
0 / 100
269 ms589824 KiB
#include <iostream> #include <vector> #include <queue> #include <unordered_map> #include <climits> using namespace std; const int INF = 1e9; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int K, N, M, O; cin >> K >> N >> M >> O; vector<vector<pair<int, int>>> graph(N); for (int i = 0; i < M; ++i) { int a, b, c; cin >> a >> b >> c; if (b / K == a / K + 1) { graph[a].emplace_back(b, c); } } vector<vector<int>> dist(N, vector<int>(N, INF)); auto dijkstra = [&](int start) { vector<int> local_dist(N, INF); priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq; local_dist[start] = 0; pq.emplace(0, start); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (d > local_dist[u]) continue; for (auto &[v, cost] : graph[u]) { if (local_dist[v] > local_dist[u] + cost) { local_dist[v] = local_dist[u] + cost; pq.emplace(local_dist[v], v); } } } dist[start] = local_dist; }; for (int i = 0; i < N; ++i) { dijkstra(i); } for (int i = 0; i < O; ++i) { int a, b; cin >> a >> b; if (dist[a][b] == INF) { cout << -1 << '\n'; } else { cout << dist[a][b] << '\n'; } } return 0; }
#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...