Submission #718286

#TimeUsernameProblemLanguageResultExecution timeMemory
718286ovidiush11Commuter Pass (JOI18_commuter_pass)C++14
0 / 100
2059 ms262144 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define ff first #define ss second const ll N = 1e5+7; ll pos[4],dis[4][N],n,m; vector<vector<pair<ll,ll>>> a; void dijkstra(ll p) { priority_queue<pair<ll,ll>> pq; pq.push({0,pos[p]}); for(ll i = 0;i < n;i++)dis[p][i] = 1e18; while(!pq.empty()) { pair<ll,ll> v = pq.top(); pq.pop(); v.ff *= -1; if(v.ff >= dis[p][v.ss])continue; dis[p][v.ss] = v.ff; for(auto x : a[v.ss])pq.push(make_pair(-(v.ff + x.ff),x.ss)); } return ; } ll in[N],len[N]; void check(ll p) { for(ll i = 0;i < n;i++)in[i] = 0; for(ll i = 0;i < n;i++)len[i] = 0; priority_queue<pair<ll,pair<ll,ll>>> pq; pq.push(make_pair(-dis[1][p],make_pair(p,p))); while(!pq.empty()) { pair<ll,pair<ll,ll>> v = pq.top(); pq.pop(); len[v.ss.ff] = max(len[v.ss.ff],len[v.ss.ss] + 1); if(in[v.ss.ff])continue; in[v.ss.ff] = 1; for(auto x : a[v.ss.ff]){ if(dis[0][x.ss] + dis[1][x.ss] == dis[1][pos[0]] && dis[1][x.ss] > dis[1][v.ss.ff]){ pq.push(make_pair(-dis[1][x.ss],make_pair(x.ss,v.ss.ff))); } } } } ll dismin[N]; void getmin(ll s) { priority_queue<pair<ll,pair<ll,ll>>> pq; if(s == 1)pq.push(make_pair(-len[pos[s]],make_pair(dis[2][pos[s]],pos[s]))); else pq.push(make_pair(len[pos[s]],make_pair(dis[2][pos[s]],pos[s]))); while(!pq.empty()) { pair<ll,pair<ll,ll>> v = pq.top(); pq.pop(); v.ss.ff = min(v.ss.ff,dis[2][v.ss.ss]); dismin[v.ss.ss] = min(dismin[v.ss.ss],v.ss.ff); for(auto x : a[v.ss.ss]) { if(in[x.ss]) { if(s == 1 && len[x.ss] > len[v.ss.ss]) { pq.push(make_pair(-len[x.ss],make_pair(v.ss.ff,x.ss))); } else if(s == 0 && len[x.ss] < len[v.ss.ss]) { pq.push(make_pair(len[x.ss],make_pair(v.ss.ff,x.ss))); } } } } return ; } int main() { cin>>n>>m; cin>>pos[0]>>pos[1]>>pos[2]>>pos[3]; pos[0]--;pos[1]--;pos[2]--;pos[3]--; a.resize(n); for(ll i = 0;i < m;i++) { ll x,y,z; cin>>x>>y>>z;x--;y--; a[x].push_back(make_pair(z,y)); a[y].push_back(make_pair(z,x)); } for(ll i = 0;i < n;i++)dismin[i] = 1e18; dijkstra(0);dijkstra(1);dijkstra(2);dijkstra(3); check(pos[1]); getmin(0); getmin(1); ll ans = dis[2][pos[3]]; for(ll i = 0;i < n;i++)if(in[i])ans = min(dismin[i] + dis[3][i],ans); cout<<ans; 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...