제출 #1039522

#제출 시각아이디문제언어결과실행 시간메모리
1039522soncaoCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
287 ms29668 KiB
#include<bits/stdc++.h> using namespace std ; #define ll long long #define ii pair<int,int> #define lll pair<ll,ll> #define vi vector<int> #define vvi vector<vector<int>> int n,m,s,t,u,v; ll du[100001],dv[100001],ds[100001],dp[2][100001],ans; bool vs[100001]; vector<lll>a[100001]; void djk1(int st, ll ar[]){ memset(vs,false,sizeof vs); for(int i=1;i<=n;i++)ar[i]=1e14; priority_queue<lll>q; q.push({0,st}); ar[st]=0; //cout<<st<<'\n'; while(q.size()){ ll w=-q.top().first,u=q.top().second; q.pop(); if(vs[u])continue; vs[u]=true; for(lll it:a[u]){ int v=it.first,w1=it.second; if(ar[v]>w1+w){ ar[v]=w1+w; q.push({-ar[v],v}); } } } } void djk2(int st,int ed){ memset(dp,31,sizeof dp); memset(vs,false,sizeof vs); priority_queue<pair<ll,lll>>q; q.push({0,{st,0}}); while(q.size()){ ll c=q.top().first,node=q.top().second.first,par=q.top().second.second; q.pop(); if(!vs[node]){ vs[node]=true; ds[node]=-c; dp[0][node]=min(du[node],dp[0][par]); dp[1][node]=min(dv[node],dp[1][par]); for(lll it:a[node])q.push({c-it.second,{it.first,node}}); }else if(-c==ds[node]){ if (min(du[node], dp[0][par]) + min(dv[node], dp[1][par]) <= dp[0][node] + dp[1][node]) { dp[0][node] = min(du[node], dp[0][par]); dp[1][node] = min(dv[node], dp[1][par]); } } } ans=min(dp[0][ed]+dp[1][ed],ans); } void sc() { cin>>n>>m>>s>>t>>u>>v; for(int i=1;i<=m;i++){ ll U,V,W;cin>>U>>V>>W; a[U].push_back({V,W}); a[V].push_back({U,W}); } djk1(u,du); djk1(v,dv); ans=du[v]; // cout<<ans<<'\n'; djk2(s,t); djk2(t,s); cout<<ans<<'\n'; } int main() { ios_base :: sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0) ; sc() ; return 0 ; ///sc }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...