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>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
int n, m, s1, e1, s2, e2;
const ll inf = 1e18;
vector<pii> G[100100];
vl dijkstra(int start){
vl dist(n);
for(int i = 0; i < n; i++) dist[i] = inf;
priority_queue<pll, vector<pll>, greater<pll>>q;
q.push({0, start});
dist[start] = 0;
while(!q.empty()){
pll x = q.top();
q.pop();
if(dist[x.second] < x.first) continue;
for(pii y : G[x.second]){
if(x.first + y.second < dist[y.first]){
dist[y.first] = x.first + y.second;
q.push({dist[y.first], y.first});
}
}
}
return dist;
}
ll pair1[2][100100], pair2[2][100100];
pair<ll,ll> st[100100];
bool ok[100100];
pll comb(pll a, pll b) {
return {min(a.first,b.first),min(a.second,b.second)};
}
int main(){
cin>>n>>m>>s1>>e1>>s2>>e2;
for(int i = 0; i < m; i++){
ll a, b, c;
cin>>a>>b>>c;
a--; b--;
G[a].pb(mp(b,c));
G[b].pb(mp(a,c));
}
// assert(false);
vl arr = dijkstra(s1);
for(int i = 0; i < n; i++) pair1[0][i] = arr[i];
arr = dijkstra(e1);
for(int i = 0; i < n; i++) pair1[1][i] = arr[i];
arr = dijkstra(s2);
for(int i = 0; i < n; i++) pair2[0][i] = arr[i];
arr = dijkstra(e2);
for(int i = 0; i < n; i++) pair2[1][i] = arr[i];
// assert(false);
for(int i = 0; i < n; i++) st[i] = {inf, inf};
ll ans = pair2[0][e2];
vector<pll> v;
memset(ok, false, sizeof ok);
for(int i = 0; i < n; i++){
if (pair1[0][i]+pair1[1][i] == pair1[0][e1]) {
ok[i] = 1;
v.pb({pair1[0][i],i});
}
}
sort(v.rbegin(),v.rend());
for (auto a: v) {
for (auto t: G[a.second]) if (ok[t.first]) st[a.second] = comb(st[a.second],st[t.first]);
ans = min(ans,min(st[a.second].first+pair2[1][a.second],st[a.second].second+pair2[0][a.second]));
st[a.second] = comb(st[a.second],{pair2[0][a.second],pair2[1][a.second]});
}
cout<<ans<<endl;
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... |