#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |