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 ll long long
const int N = 100005;
const ll INF = 1e15;
vector<pair<ll,ll>> adj[N];
// vector<pair<ll,ll>> adj2[N];
vector<ll> last[N];
ll dist1[N], dist2[N], dist3[N];
vector<ll> special;
bool ada[N], vis[N];
void djikstra1(ll start){
priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;
ll cur_node, cur_dist, next_dist, next_node;
for(int i = 0; i < N; i++){
dist1[i] = INF;
}
dist1[start] = 0;
pq.push({0,start});
while(!pq.empty()){
cur_node = pq.top().second;
cur_dist = pq.top().first;
pq.pop();
for(auto e : adj[cur_node]){
next_dist = cur_dist + e.first;
next_node = e.second;
if(dist1[next_node] < next_dist) continue;
else if(dist1[next_node] == next_dist){
last[next_node].push_back(cur_node);
}
else{
last[next_node].clear();
last[next_node].push_back(cur_node);
dist1[next_node] = next_dist;
pq.push({next_dist, next_node});
}
}
}
}
void djikstra2(ll start){
priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;
ll cur_node, cur_dist, next_dist, next_node;
for(int i = 0; i < N; i++){
dist2[i] = INF;
}
dist2[start] = 0;
pq.push({0,start});
while(!pq.empty()){
cur_node = pq.top().second;
cur_dist = pq.top().first;
pq.pop();
for(auto e : adj[cur_node]){
next_dist = cur_dist + e.first;
next_node = e.second;
if(dist2[next_node] < next_dist) continue;
// else if(dist2[next_node] == next_dist){
// last[next_node].push_back(cur_node);
// }
else{
// last[next_node].clear();
// last[next_node].push_back(cur_node);
dist2[next_node] = next_dist;
pq.push({next_dist, next_node});
}
}
}
}
void djikstra3(ll start){
priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;
ll cur_node, cur_dist, next_dist, next_node;
for(int i = 0; i < N; i++){
dist3[i] = INF;
}
dist3[start] = 0;
pq.push({0,start});
while(!pq.empty()){
cur_node = pq.top().second;
cur_dist = pq.top().first;
pq.pop();
for(auto e : adj[cur_node]){
next_dist = cur_dist + e.first;
next_node = e.second;
if(dist3[next_node] < next_dist) continue;
// else if(dist2[next_node] == next_dist){
// last[next_node].push_back(cur_node);
// }
else{
// last[next_node].clear();
// last[next_node].push_back(cur_node);
dist3[next_node] = next_dist;
pq.push({next_dist, next_node});
}
}
}
}
void finds(ll cur, ll finish){
if(cur == finish){
if(!ada[cur]){
special.push_back(cur);
ada[cur] = true;
}
return;
}
for(auto x : last[cur]){
if(vis[x]) continue;
vis[x] = true;
if(!ada[x]){
special.push_back(x);
ada[x] = true;
}
finds(x, finish);
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n, m, s, t, u, v, mindist = INF, mindist2 = INF, mindisttotal = INF;
ll input1, input2, input3;
cin >> n >> m >> s >> t >> u >> v;
for(int i = 0; i < m; i++){
cin >> input1 >> input2 >> input3;
adj[input1].push_back({input3, input2});
adj[input2].push_back({input3, input1});
// adj2[input2].push_back({input3, input1});
}
for(int i = 0 ; i< N; i++){
ada[i] = false;
vis[i] = false;
}
if(s == u){
djikstra1(s);
finds(t, s);
special.push_back(s);
special.push_back(t);
// sort(special.begin(), special.end());
// special.erase(unique(special.begin(), special.end()), special.end());
djikstra2(v);
for(auto x : special){
mindist = min(mindist, dist2[x]);
// cout << x << " " << dist2[x] << endl;
}
mindist = min(mindist, dist2[u]);
// for(int i = 1; i <= n; i++){
// for(auto x : last[i]){
// cout << i << ":" << x << " ";
// }
// cout << endl;
// }
cout << mindist;
return 0;
}
else{
djikstra1(s);
finds(t, s);
special.push_back(s);
special.push_back(t);
// sort(special.begin(), special.end());
// special.erase(unique(special.begin(), special.end()), special.end());
djikstra2(v);
for(auto x : special){
mindist = min(mindist, dist2[x]);
// cout << x << " " << dist2[x] << endl;
}
djikstra3(u);
for(auto x : special){
mindist2 = min(mindist2, dist3[x]);
// cout << x << " " << dist2[x] << endl;
}
mindisttotal = min(mindist+mindist2, dist3[v]);
cout << mindisttotal;
}
}
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |