#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (ll)1e18;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, M, S, T, U, V;
cin >> N >> M >> S >> T >> U >> V;
vector<vector<pair<int,int>>> adj(N+1);
for(int i = 0; i < M; i++){
int A, B, C;
cin >> A >> B >> C;
adj[A].emplace_back(B,C);
adj[B].emplace_back(A,C);
}
auto dijkstra = [&](int src){
vector<ll> dist(N+1, INF);
priority_queue<pair<ll,int>,
vector<pair<ll,int>>,
greater<>> pq;
dist[src] = 0;
pq.push({0, src});
while(!pq.empty()){
auto [d, x] = pq.top(); pq.pop();
if(d > dist[x]) continue;
for(auto [y, w] : adj[x]){
if(d + w < dist[y]){
dist[y] = d + w;
pq.push({dist[y], y});
}
}
}
return dist;
};
// 1) three Dijkstra’s
auto du = dijkstra(U);
auto dv = dijkstra(V);
auto ds = dijkstra(S);
auto dt = dijkstra(T);
ll D = ds[T];
if(D == INF){
cout << "-1\n";
return 0;
}
// 2) Build the shortest-path DAG from S
vector<vector<int>> dag(N+1), rdag(N+1);
for(int x = 1; x <= N; x++){
for(auto [y, w] : adj[x]){
if(ds[x] + w == ds[y]){
dag[x].push_back(y);
rdag[y].push_back(x);
}
}
}
// 3) Forward DP on dag to get F[i] = min dv[] on some S→i prefix
vector<ll> F(N+1, INF);
F[S] = dv[S];
// nodes sorted by increasing ds[]
vector<int> order(N);
iota(order.begin(), order.end(), 1);
sort(order.begin(), order.end(),
[&](int a, int b){ return ds[a] < ds[b]; });
for(int x : order){
if(F[x] == INF) continue;
for(int y : dag[x]){
ll cand = min(F[x], dv[y]);
if(cand < F[y]) F[y] = cand;
}
}
// 4) Backward DP on rdag to get G[i] = min dv[] on some i→T suffix
vector<ll> G(N+1, INF);
G[T] = dv[T];
// same order, but decreasing ds[]
sort(order.begin(), order.end(),
[&](int a, int b){ return ds[a] > ds[b]; });
for(int x : order){
if(G[x] == INF) continue;
for(int p : rdag[x]){
ll cand = min(G[x], dv[p]);
if(cand < G[p]) G[p] = cand;
}
}
// 5) Over all i on some shortest S→T path (ds[i]+dt[i] == D),
// minimize du[i] + min(F[i], G[i])
ll ans = INF;
for(int i = 1; i <= N; i++){
if(ds[i] + dt[i] == D){
// i lies on at least one shortest S→T
ll bestDvOnPath = min(F[i], G[i]);
if(bestDvOnPath < INF && du[i] < INF){
ans = min(ans, du[i] + bestDvOnPath);
}
}
}
cout << ans << "\n";
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... |