제출 #781275

#제출 시각아이디문제언어결과실행 시간메모리
781275andecaandeciCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
330 ms36172 KiB
#include <bits/stdc++.h> using namespace std; # define int long long # define fir first # define sec second # define pb push_back const int cnst = 2e5+5; bool mutipletestcase = 0; //bool debug = false; int n, m; int s, t, u, v; int shor[cnst]; int dis[cnst]; int dist[cnst]; vector<pair<int, int>> vec[cnst]; void djikstrast() { bool vis[n+5]; priority_queue<tuple<int, int>, vector<tuple<int, int>>, greater<tuple<int, int>>> pq; pq.push({0, s}); memset(vis, 0, sizeof(vis)); while(!pq.empty()) { auto[x, idx] = pq.top(); pq.pop(); if(vis[idx]) continue; vis[idx] = 1; dis[idx] = x; for(auto v: vec[idx]) { if(!vis[v.fir]) pq.push({x+v.sec, v.fir}); } } pq.push({0, t}); memset(vis, 0, sizeof(vis)); while(!pq.empty()) { auto[x, idx] = pq.top(); pq.pop(); if(vis[idx]) continue; vis[idx] = 1; dist[idx] = x; for(auto v: vec[idx]) { if(!vis[v.fir]) pq.push({x+v.sec, v.fir}); } } for(int i = 1; i<=n; i++) if(dis[i]+dist[i] == dis[t]) shor[i] = 1; // for(int i = 1; i<=n; i++) cerr << shor[i] << " "; cerr << endl; // for(int i = 1; i<=n; i++) cerr << dis[i] << " "; cerr << endl; } void djikstrauv() { bool vis[n+5][5]; memset(vis, 0, sizeof(vis)); priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq; pq.push({0, u, 0}); if(shor[u]) pq.push({0, u, 1}), pq.push({0, u, 2}); while(!pq.empty()) { auto[x, idx, id] = pq.top(); pq.pop(); if(vis[idx][id] || idx == 0) continue; vis[idx][id] = 1; // cerr << x << " " << idx << " " << id << endl; if(idx == v) { cout << x << endl; return; } if(id == 0) { for(auto v: vec[idx]) { if(!vis[v.fir][0]) pq.push({x+v.sec, v.fir, 0}); if(shor[v.fir] && shor[idx]) { if(!vis[v.fir][1] && dis[v.fir] < dis[idx]) pq.push({x, v.fir, 1}); if(!vis[v.fir][2] && dis[v.fir] > dis[idx]) pq.push({x, v.fir, 2}); } } } else if(id == 1) { for(auto v: vec[idx]) { if(!vis[v.fir][3]) pq.push({x+v.sec, v.fir, 3}); if(shor[v.fir] && dis[v.fir] < dis[idx]) pq.push({x, v.fir, 1}); } } else if(id == 2) { for(auto v: vec[idx]) { if(!vis[v.fir][3]) pq.push({x+v.sec, v.fir, 3}); if(shor[v.fir] && dis[v.fir] > dis[idx]) pq.push({x, v.fir, 2}); } } else { for(auto v: vec[idx]) if(!vis[v.fir][3]) pq.push({x+v.sec, v.fir, 3}); } } } void solve() { cin >> n >> m >> s >> t >> u >> v; for(int i = 1; i<=m; i++) { int a, b, c; cin >> a >> b >> c; vec[a].pb({b, c}); vec[b].pb({a, c}); } djikstrast(); djikstrauv(); } signed main() { ios_base::sync_with_stdio(false); int t = 1; if(mutipletestcase) cin >> t; while(t--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...