제출 #1015962

#제출 시각아이디문제언어결과실행 시간메모리
1015962KryzCommuter Pass (JOI18_commuter_pass)C++17
15 / 100
2009 ms262144 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define fi first #define se second #define sst string #define pb push_back #define maxco 100000+5 #define lld long double #define cha ios_base::sync_with_stdio(false); #define ffl cout.flush(); #define phi acos(-1) #define mr make_pair #define REP(i,a,b) for (int i = a; i <= b; i++) #define pqin priority_queue<ll,vector<ll>,greater<>> #define pqpair priority_queue<pair<ll,ll> ,vector<pair<ll,ll>>,greater<pair<ll,ll>>> #define pqpair2 priority_queue<pair<pair<ll,ll>,pair<ll,ll>>,vector<pair<pi,pair<ll,ll>>>,greater<pair<pi,pair<ll,ll>>>> #define INF 1000000009 #define MAXN 200069 #define pii pair<ll,ll> #define mod 998244353 ll n,m; ll s,t,u,v; vector <pii> vec[MAXN]; ll dist[5][MAXN]; vector <ll> bc[MAXN]; bool vis[MAXN]; void djikstra(ll idx,ll in){ priority_queue<pair<ll,ll> ,vector <pair<ll,ll>>,greater<pair<ll,ll>>> pq; pq.push({0,in}); dist[idx][in]=0; while(!pq.empty()){ ll cost=pq.top().fi; ll fr=pq.top().se; pq.pop(); if(cost>dist[idx][fr] )continue; if(vis[fr])continue; vis[fr]=1; if(vec[fr].size()){ for(auto x : vec[fr]){ if(dist[idx][x.se]>dist[idx][fr]+x.fi){ dist[idx][x.se]=dist[idx][fr]+x.fi; pq.push({dist[idx][x.se],x.se}); if(idx==3){ bc[x.se].clear(); bc[x.se].pb(fr); } } else if(dist[idx][x.se]==dist[idx][fr]+x.fi){ if(idx==3){ bc[x.se].pb(fr); } } } } } } ll dp[MAXN]; int main(){ cha cin>>n>>m; cin>>s>>t>>u>>v; REP(i,1,4)REP(j,1,n)dist[i][j]=1e18; REP(i,1,n)dp[i]=1e18; REP(i,1,m){ ll u,v,w; cin>>u>>v>>w; vec[u].pb({w,v}); vec[v].pb({w,u}); } REP(i,1,n)vis[i]=0; djikstra(1,u); REP(i,1,n)vis[i]=0; djikstra(2,v); REP(i,1,n)vis[i]=0; djikstra(3,s); queue<ll> q; q.push(t); while(q.size()){ ll node=q.front(); q.pop(); for(auto x : bc[node]){ q.push(x); } } ll ans=1e18; priority_queue<pair<pii,pair<ll,ll>> ,vector <pair<pii,pii>>,greater<pair<pii,pii>>> pq; pq.push({{dist[1][t]+dist[2][t],t},{dist[1][t],dist[2][t]}}); dp[t]=dist[1][t]+dist[2][t]; ans=dp[t]; while(pq.size()){ ll node=pq.top().fi.se; ll bf1=pq.top().se.fi; ll bf2=pq.top().se.se; ll cost=pq.top().fi.fi; pq.pop(); if(cost>dp[node] )continue; ans=min(ans,dp[node]); if(bc[node].size()){ for(auto x : bc[node]){ ll nwx=min(bf1,dist[1][x]); ll nwy=min(bf2,dist[2][x]); if(dp[x]>nwx+nwy){ dp[x]=nwx+nwy; pq.push({{dp[x],x},{nwx,nwy}}); } } } } ans=min(dist[1][v],ans); cout<<ans<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...