This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define int long long
using namespace std;
ll MAX = 1e18;
int N, M, S, T, U, V;
ll answer;
vector<vector<pair<int,ll>>> adj;
vector<bool> processed;
vector<ll> distS, distT, distU, distV;
vector<pair<ll,ll>> memo;
pair<ll, ll> res(int pos) {
if (pos == T) return {distU[T], distV[T]};
if (memo[pos] != make_pair(MAX, MAX)) return memo[pos];
processed[pos] = true;
pair<ll, ll> best = {MAX, MAX};
for (auto x : adj[pos]) {
if (!processed[x.fi]) {
if (distT[x.fi] + distS[x.fi] == distS[T]) {
pair<ll, ll> func = res(x.fi);
if (distU[pos] <= func.fi) { func.fi = distU[pos]; answer = min(answer, func.fi + func.se); }
if (distV[pos] <= func.se) { func.se = distV[pos]; answer = min(answer, func.fi + func.se); }
best.fi = min(best.fi, func.fi);
best.se = min(best.se, func.se);
}
}
}
processed[pos] = false;
return memo[pos] = best;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> M >> S >> T >> U >> V;
S--, T--, U--, V--;
adj.resize(N); memo.resize(N, {MAX, MAX}); processed.resize(N, false);
for (int i = 0; i < M; i++) {
int a, b; ll c; cin >> a >> b >> c;
a--, b--;
adj[a].push_back({b,c});
adj[b].push_back({a,c});
}
distS.resize(N, MAX); distT.resize(N, MAX); distU.resize(N, MAX); distV.resize(N, MAX);
priority_queue < pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll,int>>> q;
q.push({0, S}); distS[S] = 0;
while (!q.empty()) {
int x = q.top().se; q.pop();
if (processed[x]) continue;
processed[x] = true;
for (auto w : adj[x]) {
if (distS[w.fi] > distS[x] + w.se) {
distS[w.fi] = distS[x] + w.se;
q.push({distS[w.fi], w.fi});
}
}
}
processed.clear(); processed.resize(N, false);
q.push({0,T}); distT[T] = 0;
while (!q.empty()) {
int x = q.top().se; q.pop();
if (processed[x]) continue;
processed[x] = true;
for (auto w : adj[x]) {
if (distT[w.fi] > distT[x] + w.se) {
distT[w.fi] = distT[x] + w.se;
q.push({distT[w.fi], w.fi});
}
}
}
processed.clear(); processed.resize(N,false);
q.push({0,U}); distU[U] = 0;
while (!q.empty()) {
int x = q.top().se; q.pop();
if (processed[x]) continue;
processed[x] = true;
for (auto w : adj[x]) {
if (distU[w.fi] > distU[x] + w.se) {
distU[w.fi] = distU[x] + w.se;
q.push({distU[w.fi], w.fi});
}
}
}
processed.clear(); processed.resize(N, false);
q.push({0, V}); distV[V] = 0;
while (!q.empty()) {
int x = q.top().se; q.pop();
if (processed[x]) continue;
processed[x] = true;
for (auto w : adj[x]) {
if (distV[w.fi] > distV[x] + w.se) {
distV[w.fi] = distV[x] + w.se;
q.push({distV[w.fi], w.fi});
}
}
}
processed.clear(); processed.resize(N, false);
answer = min(distU[T] + distV[T], distU[V]);
res(S);
cout << answer << '\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... |