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 <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <map>
#include <climits>
#include <cmath>
#include <set>
#include <algorithm>
#include <stack>
using namespace std;
#define speedup ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define ll long long
vector<ll> distU, distV;
vector<vector<pair<int, int>>> graph;
int n, m;
int s, t;
int u, v;
vector<ll> dijstra(int st){
vector<ll> dist(n, LLONG_MAX);
dist[st] = 0;
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
pq.push({0, st});
while (!pq.empty()){
int c = pq.top().second; pq.pop();
for (pair<int, int> p: graph[c]){
if (dist[p.first] > dist[c]+p.second){
dist[p.first] = dist[c]+p.second;
pq.push({dist[p.first], p.first});
}
}
}
return dist;
}
ll dijstra2(int start, int end){
vector<ll> dU(n, LLONG_MAX), dV(n, LLONG_MAX);
vector<ll> dist(n, LLONG_MAX);
priority_queue<pair<ll, pair<int, int>>, vector<pair<ll, pair<int, int>>>, greater<pair<ll, pair<int, int>>>> pq;
pq.push({0, {start, 0}});
dist[start] = 0;
vector<bool> vis(n, false);
while (!pq.empty()){
ll cdist = pq.top().first; int cur = pq.top().second.first, par = pq.top().second.second; pq.pop();
if (!vis[cur]){
vis[cur] = true;
dU[cur] = min(distU[cur], dU[par]);
dV[cur] = min(distV[cur], dV[par]);
for (pair<int, int> p: graph[cur]){
pq.push({cdist+p.second, {p.first, cur}});
}
}else if (cdist == dist[cur] && min(dU[par], distU[cur])+min(dV[par], distV[cur]) <= dU[cur]+dV[cur]){
dU[cur] = min(dU[cur], dU[par]);
dV[cur] = min(dV[cur], dV[par]);
for (pair<int, int> p: graph[cur]){
pq.push({cdist+p.second, {p.first, cur}});
}
}
}
return dU[end]+dV[end];
}
int main(){
speedup
cin >> n >> m;
cin >> s >> t;
cin >> u >> v;
graph.resize(n);
s--, t--, u--, v--;
for (int i = 0; i < m; i++){
int a, b, w; cin >> a >> b >> w;
a--, b--;
graph[a].push_back({b, w});
graph[b].push_back({a, w});
}
distU = dijstra(u);
distV = dijstra(v);
ll a1 = dijstra2(s, t);
ll a2 = dijstra2(t, s);
cout << min(a1, a2) << 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... |