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>
#define int long long
using namespace std;
const int N=1e5+2;
const int inf=1e18+2;
priority_queue<pair<int,int> > lis;
vector<pair<int,int> > adj[N];
int dis[N],dis1[N],ans=inf,min1[N],dis2[N],min2[N],dis3[N];
void dijkstra(int x){
for(int i=0;i<adj[x].size();i++){
if(dis[adj[x][i].first]>dis[x]+adj[x][i].second){
dis[adj[x][i].first]=dis[x]+adj[x][i].second;
lis.push({-dis[adj[x][i].first],adj[x][i].first});
}
}
}
void dijkstra1(int x){
for(int i=0;i<adj[x].size();i++){
if(dis1[adj[x][i].first]>dis1[x]+adj[x][i].second){
dis1[adj[x][i].first]=dis1[x]+adj[x][i].second;
lis.push({-dis1[adj[x][i].first],adj[x][i].first});
}
}
}
void dijkstra3(int x){
for(int i=0;i<adj[x].size();i++){
if(dis3[adj[x][i].first]>dis3[x]+adj[x][i].second){
dis3[adj[x][i].first]=dis3[x]+adj[x][i].second;
lis.push({-dis3[adj[x][i].first],adj[x][i].first});
}
}
}
void dijkstra2(int x){
for(int i=0;i<adj[x].size();i++){
if(dis2[adj[x][i].first]>dis2[x]+adj[x][i].second){
dis2[adj[x][i].first]=dis2[x]+adj[x][i].second;
min1[adj[x][i].first]=min(min1[adj[x][i].first],min1[x]);
min2[adj[x][i].first]=min(min2[adj[x][i].first],min2[x]);
lis.push({-dis2[adj[x][i].first],adj[x][i].first});
}
else{
if(dis2[adj[x][i].first]==dis2[x]+adj[x][i].second){
min1[adj[x][i].first]=min(min1[adj[x][i].first],min1[x]);
min2[adj[x][i].first]=min(min2[adj[x][i].first],min2[x]);
}
}
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n,m,s,t,u,v,i,j,k,l;
cin>>n>>m>>s>>t>>u>>v;
for(i=1;i<=n;i++){
dis[i]=inf;
dis1[i]=inf;
dis3[i]=inf;
dis2[i]=inf;
}
for(i=1;i<=m;i++){
cin>>j>>k>>l;
adj[j].push_back({k,l});
adj[k].push_back({j,l});
}
dis[u]=0;
lis.push({0,u});
while(lis.size()){
if(-lis.top().first==dis[lis.top().second]){
dijkstra(lis.top().second);
}
lis.pop();
}
dis1[v]=0;
lis.push({0,v});
while(lis.size()){
if(-lis.top().first==dis1[lis.top().second]){
dijkstra1(lis.top().second);
}
lis.pop();
}
dis3[t]=0;
lis.push({0,t});
while(lis.size()){
if(-lis.top().first==dis3[lis.top().second]){
dijkstra3(lis.top().second);
}
lis.pop();
}
dis2[s]=0;
lis.push({0,s});
for(i=1;i<=n;i++){
min1[i]=dis[i];
min2[i]=dis1[i];
}
ans=dis[v];
while(lis.size()){
if(-lis.top().first==dis2[lis.top().second]){
if(dis2[lis.top().second]+dis3[lis.top().second]==dis3[s]){
ans=min(ans,min1[lis.top().second]+dis1[lis.top().second]);
ans=min(ans,min2[lis.top().second]+dis[lis.top().second]);
}
dijkstra2(lis.top().second);
//cout<<lis.top().second<<" "<<ans<<endl;
}
lis.pop();
}
cout<<ans;
}
Compilation message (stderr)
commuter_pass.cpp: In function 'void dijkstra(long long int)':
commuter_pass.cpp:12:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<adj[x].size();i++){
~^~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void dijkstra1(long long int)':
commuter_pass.cpp:20:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<adj[x].size();i++){
~^~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void dijkstra3(long long int)':
commuter_pass.cpp:28:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<adj[x].size();i++){
~^~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void dijkstra2(long long int)':
commuter_pass.cpp:36:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<adj[x].size();i++){
~^~~~~~~~~~~~~~
# | 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... |