Submission #1274712

#TimeUsernameProblemLanguageResultExecution timeMemory
1274712kduckpCommuter Pass (JOI18_commuter_pass)C++20
15 / 100
598 ms49620 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll INF = 1e18; const int N = 1e5 + 5; vector<pair<int, ll>> adj[N]; int n, m, a, b, c, d; vector<pair<int, int>> edges; map<pair<int, int>, int> edge_id; ll w[N * 2]; bool is_vip[N * 2]; vector<int> dijkstra_path(int src, int dst, ll* cost) { vector<ll> dist(n + 1, INF); vector<int> prev(n + 1, -1); priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq; dist[src] = 0; pq.push({0, src}); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (d > dist[u]) continue; for (auto [v, eid] : adj[u]) { ll c = cost[eid]; if (dist[v] > dist[u] + c) { dist[v] = dist[u] + c; prev[v] = u; pq.push({dist[v], v}); } } } vector<int> path; int cur = dst; while (cur != -1) { path.push_back(cur); cur = prev[cur]; } reverse(path.begin(), path.end()); return path; } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m >> a >> b >> c >> d; for (int i = 1; i <= m; i++) { int u, v; ll ww; cin >> u >> v >> ww; adj[u].push_back({v, i}); adj[v].push_back({u, i}); edges.push_back({u, v}); edge_id[{u, v}] = i; edge_id[{v, u}] = i; w[i] = ww; } ll cost1[N * 2]; for (int i = 1; i <= m; i++) cost1[i] = w[i]; vector<int> path = dijkstra_path(a, b, cost1); for (int i = 1; i < path.size(); i++) { int u = path[i - 1], v = path[i]; int eid = edge_id[{u, v}]; is_vip[eid] = true; } ll cost2[N * 2]; for (int i = 1; i <= m; i++) cost2[i] = is_vip[i] ? 0 : w[i]; vector<ll> dist(n + 1, INF); priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq; dist[c] = 0; pq.push({0, c}); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (d > dist[u]) continue; for (auto [v, eid] : adj[u]) { ll c = cost2[eid]; if (dist[v] > dist[u] + c) { dist[v] = dist[u] + c; pq.push({dist[v], v}); } } } cout << dist[d] << endl; 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...