Submission #1241950

#TimeUsernameProblemLanguageResultExecution timeMemory
1241950trantien3771Commuter Pass (JOI18_commuter_pass)C++20
15 / 100
133 ms26320 KiB
#include <bits/stdc++.h> #define int long long using namespace std; const int MAXN = 200000 + 5; const int INF = LLONG_MAX / 4; int n, m; int A, B, C, D; vector<pair<int,int>> adj[MAXN]; int dist_ab[MAXN], dist_cd[MAXN], parent[MAXN]; bool on_path[MAXN]; void dijkstra(int src, int dist[], bool record_parent) { fill(dist + 1, dist + n + 1, INF); if (record_parent) fill(parent + 1, parent + n + 1, -1); dist[src] = 0; priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq; pq.push({0, src}); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (d != dist[u]) continue; for (auto [v, w] : adj[u]) { if (dist[v] > d + w) { dist[v] = d + w; if (record_parent) parent[v] = u; pq.push({dist[v], v}); } } } } int32_t main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m >> A >> B >> C >> D; for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; adj[u].push_back({v, w}); adj[v].push_back({u, w}); } // 1) Chạy Dijkstra từ A, ghi lại parent để xác định đường đi ngắn nhất đến B dijkstra(A, dist_ab, true); // 2) Thu hồi đường đi từ B về A vector<int> path; int cur = B; while (cur != -1) { path.push_back(cur); if (cur == A) break; cur = parent[cur]; } reverse(path.begin(), path.end()); // độ dài đường đi từ A đến B // 3) Đánh dấu các đỉnh trên đường A->B for (int u : path) on_path[u] = true; // 4) Thêm cạnh 0-weight giữa các đỉnh liên tiếp trên đường đó for (size_t i = 1; i < path.size(); i++) { int u = path[i-1], v = path[i]; adj[u].push_back({v, 0}); adj[v].push_back({u, 0}); } // 5) Chạy Dijkstra từ C trên đồ thị đã mở rộng, tìm đến D dijkstra(C, dist_cd, false); long long answer = dist_cd[D]; if (answer >= INF/2) cout << -1; else cout << answer; 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...