Submission #1183670

#TimeUsernameProblemLanguageResultExecution timeMemory
1183670meicrisToll (BOI17_toll)C++17
18 / 100
3095 ms4480 KiB
#include <iostream> #include <vector> #include <queue> #include <unordered_map> #include <unordered_set> 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); } } unordered_map<int, vector<pair<int, int>>> ordenesAgrupadas; vector<pair<int, int>> todasLasOrdenes; for (int i = 0; i < O; ++i) { int a, b; cin >> a >> b; ordenesAgrupadas[a].emplace_back(i, b); todasLasOrdenes.emplace_back(a, b); } vector<int> respuestas(O, -1); for (auto &[origen, destinos] : ordenesAgrupadas) { vector<int> dist(N, INF); priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq; dist[origen] = 0; pq.emplace(0, origen); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (d > dist[u]) continue; for (auto &[v, costo] : graph[u]) { if (dist[v] > dist[u] + costo) { dist[v] = dist[u] + costo; pq.emplace(dist[v], v); } } } for (auto &[idx, destino] : destinos) { if (dist[destino] < INF) { respuestas[idx] = dist[destino]; } } } for (int r : respuestas) cout << r << '\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...