제출 #853959

#제출 시각아이디문제언어결과실행 시간메모리
853959parsadox2Commuter Pass (JOI18_commuter_pass)C++14
100 / 100
425 ms94696 KiB
#include <bits/stdc++.h> #define int long long using namespace std; const int N = 1e6 + 2; int n , m , s , t , ss , tt , dis[2][N] , slm[3][N]; vector <pair<int , int>> adj[N]; bool marked[N]; void dij(int star , int h[]) { memset(h , 63 , N); memset(marked , false , sizeof marked); h[star] = 0; priority_queue <pair<int , int>> pq; pq.push({0 , star}); while(!pq.empty()) { auto now = pq.top(); pq.pop(); int v = now.second , D = abs(now.first); if(marked[v]) continue; marked[v] = true; for(auto u : adj[v]) if(h[u.first] > D + u.second) { h[u.first] = D + u.second; pq.push({-h[u.first] , u.first}); } } } bool mrk[3][N]; void solve(int star) { memset(slm , 63 , sizeof slm); memset(mrk , false , sizeof mrk); slm[0][star] = 0; priority_queue <pair<int , pair<int , int>>> pq; pq.push({0 , {0 , star}}); while(!pq.empty()) { auto now = pq.top(); pq.pop(); int v = now.second.second , ty = now.second.first , D = abs(now.first); if(mrk[ty][v]) continue; mrk[ty][v] = true; for(auto u : adj[v]) { if(u.second == 0 && ty <= 1 && slm[1][u.first] > D) { slm[1][u.first] = D; pq.push({-D , {1 , u.first}}); } if(u.second > 0 && ty == 0 && slm[0][u.first] > D + u.second) { slm[0][u.first] = D + u.second; pq.push({-slm[0][u.first] , {0 , u.first}}); } if(u.second > 0 && ty >= 1 && slm[2][u.first] > D + u.second) { slm[2][u.first] = D + u.second; pq.push({-slm[2][u.first] , {2 , u.first}}); } } } } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m >> s >> t >> ss >> tt; vector <pair<pair<int , int> , int>> edges; while(m--) { int a , b , w; cin >> a >> b >> w; adj[a].push_back({b , w}); adj[b].push_back({a , w}); edges.push_back({{a , b} , w}); } dij(s , dis[0]); dij(t , dis[1]); for(auto e : edges) { int a = e.first.first , b = e.first.second , w = e.second; if(dis[0][a] + dis[1][b] + w == dis[0][t]) adj[a].push_back({b , 0}); if(dis[0][b] + dis[1][a] + w == dis[0][t]) adj[b].push_back({a , 0}); } solve(ss); int ans = min({slm[0][tt] , slm[1][tt] , slm[2][tt]}); solve(tt); ans = min({ans , slm[0][ss] , slm[1][ss] , slm[2][ss]}); cout << ans << '\n'; 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...