#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair < ll, ll >;
using plll = pair < ll, pll >;
const ll N = 1e5 + 2;
vector < pll > adj[N];
ll Du[N], Dv[N], n, fn, E[2][N], Di[N], D[N], used[N];
void Djikstra(ll x) {
ll i, cost, X;
priority_queue < pll, vector < pll>, greater < pll > > pq;
for (i =0; i <= n; i ++) D[i] = 1e18;
pq.push(make_pair(0, x));
D[x] = 0;
while(!pq.empty()) {
x = pq.top().second;
cost = pq.top().first;
pq.pop();
if ( D[x] != cost) continue;
for ( pll P: adj[x]) {
X = P.first;
if ( D[X] > D[x] + P.second) {
D[X] = D[x] + P.second;
pq.push({D[X], X});
}
}
}
return ;
}
ll ans;
void Djikstra1(ll x, ll y) {
ll i, cost, type, par, X;
priority_queue < pll, vector < pll>, greater < pll > > pq;
for (i =0; i <= n; i ++) E[1][i] = E[0][i] = 1e18, used[i] = 0, Di[i] = 1e18;
pq.push(make_pair(0, x));
E[0][x] = Du[x];
E[1][x] = Dv[x];
Di[x] = 0;
while(!pq.empty()) {
x = pq.top().second;
cost = pq.top().first;
pq.pop();
if ( Di[x] != cost) continue;
for ( pll P : adj[x]) {
X = P.first;
if (Di[X] < Di[x] + P.second) continue;
if ( Di[X] > Di[x] + P.second) {
E[0][X] = min(E[0][x], Du[X]);
E[1][X] = min(E[1][x], Dv[X]);
Di[X] = cost + P.second;
pq.push(make_pair(cost + P.second, X));
}
else {
if (min(E[0][x], Du[X]) + min(E[1][x], Dv[X]) < E[0][X] + E[1][X]) {
E[0][X] = min(E[0][x], Du[X]);
E[1][X] = min(E[1][x], Dv[X]);
}
}
}
}
ans = min(ans, E[0][y] + E[1][y]);
return ;
}
int main() {
ll m, r, x, y, i,u, v, s, X, j, t, c,st, st1, fn1;
cin >> n >> m;
cin >> s >> t;
cin >> u >> v;
for (i = 1; i <= m; i ++) {
cin >> x >> y >> c;
adj[x].push_back({y, c});
adj[y].push_back({x, c});
}
Djikstra(u);
for (i = 0; i <= n; i ++) Du[i]= D[i];
Djikstra(v);
for (i = 0; i <= n; i ++) Dv[i]= D[i];
ans= Du[v];
Djikstra1(s, t);
Djikstra1(t, s);
cout << ans << endl;
}
# | 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... |