Submission #868440

#TimeUsernameProblemLanguageResultExecution timeMemory
868440amirhoseinfar1385Commuter Pass (JOI18_commuter_pass)C++17
0 / 100
94 ms18836 KiB
#include<bits/stdc++.h> using namespace std; const int maxn=100000+10,maxm=200000+10; struct yal{ int u,v,w,te,dov; int getad(int fu){ int ret=(u^v^fu); return ret; } }; yal alled[maxn]; vector<int>adj[maxn]; long long dis[maxn]; long long inf=1e15; int n,m,s,t,fu,fv,vis[maxn]; void firstdij(){ set<pair<int,pair<int,int>>>st; for(auto x:adj[s]){ st.insert(make_pair(alled[x].w,make_pair(alled[x].getad(s),x))); } dis[s]=0; while((int)st.size()>0){ auto x=*st.begin(); st.erase(x); if(x.first>dis[x.second.first]){ continue; } alled[x.second.second].dov=1; dis[x.second.first]=x.first; if(alled[x.second.second].u==x.second.first){ swap(alled[x.second.second].u,alled[x.second.second].v); } for(auto y:adj[x.second.first]){ st.insert(make_pair(alled[y].w+x.first,make_pair(alled[y].getad(x.second.first),y))); } } } void dfs(int u){ if(vis[u]==1){ return ; } vis[u]=1; for(auto x:adj[u]){ if(alled[x].v==u&&alled[x].dov==1){ alled[x].te=1; dfs(alled[x].u); } } } int visd[maxn][5]; long long dij(){ set<pair<long long ,pair<int,int>>>st; st.insert(make_pair(0,make_pair(fu,0))); while((int)st.size()>0){ auto x=*st.begin(); st.erase(x); // cout<<x.first<<" "<<x.second.first<<" "<<x.second.second<<"\n"; if(visd[x.second.first][x.second.second]==1){ continue; } visd[x.second.first][x.second.second]=1; if(x.second.first==fv){ return x.first; } for(auto y:adj[x.second.first]){ if(alled[y].te){ if(x.second.second==0){ if(alled[y].u==x.second.first){ st.insert(make_pair(x.first,make_pair(alled[y].getad(x.second.first),1))); } else{ st.insert(make_pair(x.first,make_pair(alled[y].getad(x.second.first),2))); } st.insert(make_pair(x.first+alled[y].w,make_pair(alled[y].getad(x.second.first),0))); } if(x.second.second==1){ if(alled[y].u==x.second.first){ st.insert(make_pair(x.first,make_pair(alled[y].getad(x.second.first),1))); } else{ // st.insert(make_pair(x.first,make_pair(alled[y].getad(x.second.first),2))); } st.insert(make_pair(x.first+alled[y].w,make_pair(alled[y].getad(x.second.first),3))); } if(x.second.second==2){ if(alled[y].u==x.second.first){ // st.insert(make_pair(x.first,make_pair(alled[y].getad(x.second.first),1))); } else{ st.insert(make_pair(x.first,make_pair(alled[y].getad(x.second.first),2))); } st.insert(make_pair(x.first+alled[y].w,make_pair(alled[y].getad(x.second.first),3))); } if(x.second.second==3){ if(alled[y].u==x.second.first){ // st.insert(make_pair(x.first,make_pair(alled[y].getad(x.second.first),1))); } else{ // st.insert(make_pair(x.first,make_pair(alled[y].getad(x.second.first),2))); } st.insert(make_pair(x.first+alled[y].w,make_pair(alled[y].getad(x.second.first),3))); } } else{ if(x.second.second==0){ st.insert(make_pair(x.first+alled[y].w,make_pair(alled[y].getad(x.second.first),0))); } if(x.second.second==1){ st.insert(make_pair(x.first+alled[y].w,make_pair(alled[y].getad(x.second.first),3))); } if(x.second.second==2){ st.insert(make_pair(x.first+alled[y].w,make_pair(alled[y].getad(x.second.first),3))); } if(x.second.second==3){ st.insert(make_pair(x.first+alled[y].w,make_pair(alled[y].getad(x.second.first),3))); } } } } return 0; } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); for(int i=0;i<maxn;i++){ dis[i]=inf; } cin>>n>>m; cin>>s>>t; cin>>fu>>fv; for(int i=0;i<m;i++){ cin>>alled[i].u>>alled[i].v>>alled[i].w; adj[alled[i].u].push_back(i); adj[alled[i].v].push_back(i); } firstdij(); //cout<<"salam"<<endl; dfs(t); cout<<dij()<<"\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...