| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 869360 | vjudge1 | Commuter Pass (JOI18_commuter_pass) | C++17 | 0 ms | 0 KiB |
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 fr first
#define sc second
#define ll long long int
const int mxn=1e5+5;
ll n,m,dis[mxn],s,t,u,v,ans=1e18,mark[mxn];
pair<int,int>par2[mxn];
vector<int>par[mxn];
set<pair<ll,ll> >st,yal[mxn];
void dfs(int z){
mark[z]=1;
dis[z]=0;
for(auto i:par[z]){
if(!mark[i]){
dfs(i);
}
}
}
void dij(){
while(st.size()){
auto x=*st.begin();
st.erase({x.fr,x.sc});
for(auto i:yal[x.sc]){
if(dis[i.fr]>x.fr+i.sc){
st.erase({dis[i.fr],i.fr});
dis[i.fr]=x.fr+i.sc;
st.insert({dis[i.fr],i.fr});
par2[i.fr].fr=x.sc;
par2[i.fr].sc=i.sc;
par[i.fr].clear();
par[i.fr].push_back(x.sc);
}
else if(dis[i.fr]==x.fr+i.sc){
par[i.fr].push_back(x.sc);
}
}
}
int main(){
cin>>n>>m;
cin>>s>>t>>u>>v;
for(int i=1;i<=m;i++){
int x,y,w;
cin>>x>>y>>w;
yal[x].insert({y,w});
yal[y].insert({x,w});
}
for(int i=1;i<=n;i++){
dis[i]=(i==s)?0:1e18;
st.insert({dis[i],i});
}
dij();
if(s!=u){
for(int x=t;par2[x].fr!=0;x=par2[x].fr){
yal[x].erase({par2[x].fr,par2[x].sc});
yal[x].insert({par2[x].fr,0});
yal[par2[x].fr].erase({x,par2[x].sc});
yal[par2[x].fr].insert({x,0});
}for(int i=1;i<=n;i++){
dis[i]=(i==u)?0:1e18;
st.insert({dis[i],i});
}
}
else{
for(int i=1;i<=n;i++){
dis[i]=1e18;
}
dfs(t);
for(int i=1;i<=n;i++){
st.insert({dis[i],i});
}
}
dij();
cout<<dis[v];
}