Submission #1167589

#TimeUsernameProblemLanguageResultExecution timeMemory
1167589mareksbCommuter Pass (JOI18_commuter_pass)C++20
0 / 100
151 ms10576 KiB
#include <bits/stdc++.h> using namespace std; const int N=100005; vector<pair<int,int>> mas[N]; int dS[N]; int dT[N]; int dV[N]; int dU[N]; int n,m; int s,t;//commuter pass int u,v; void dijkstra(int start, int* dist){ priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq; dist[start]=0; pq.push({0,start}); while(!pq.empty()){ int x=pq.top().second; pq.pop(); for(auto p:mas[x]){ if(dist[x]+p.second<dist[p.first]){ dist[p.first]=dist[x]+p.second; pq.push({dist[p.first],p.first}); } } } } void dijkstra2(int start, int* dist){ priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq; dist[start]=0; pq.push({0,start}); while(!pq.empty()){ int x=pq.top().second; pq.pop(); for(auto p:mas[x]){ int cost=p.second; if(dS[x]+dT[x]==dS[t]&&dS[p.first]+dT[p.first]==dS[t]){ cost=0; } if(dist[x]+cost<dist[p.first]){ dist[p.first]=dist[x]+cost; pq.push({dist[p.first],p.first}); } } } } void solve(){ cin>>n>>m; for(int i=0;i<=n;i++){ dS[i]=N; dT[i]=N; dV[i]=N; dU[i]=N; } cin>>s>>t; cin>>u>>v; for(int i=0;i<m;i++){ int x,y,c; cin>>x>>y>>c; mas[x].push_back({y,c}); mas[y].push_back({x,c}); } dijkstra(s,dS); dijkstra(t,dT); dijkstra2(v,dV); dijkstra2(u,dU); int ans=INT_MAX; for(int i=1;i<=n;i++){ //cout<<"i: "<<i<<' '<<dS[i]<<' '<<dT[i]<<'\n'; if(dS[i]+dT[i]==dS[t]){ ans=min(ans,dV[i]+dU[i]); } } cout<<ans<<'\n'; } int main() { //ios_base::sync_with_stdio(false);cin.tie(NULL); int t=1; //cin>>t; while(t--){ solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...