제출 #595328

#제출 시각아이디문제언어결과실행 시간메모리
595328WaelCommuter Pass (JOI18_commuter_pass)C++17
0 / 100
496 ms67580 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; //#define int long long //#define endl '\n' #define F first #define S second int const M = 1e6 + 10 , N = 1e3 + 10 , mod = 1e9 + 7; ll T , n , m , k , cost , x , y , s , t , u , v , type , ans = 1e18 , dis[6][M] , cnt[M] , on[M] , U[M] , V[M]; int dx[] = {1 , -1 , 0 , 0} , dy[] = {0 , 0 , 1 , -1}; priority_queue<pair<ll , ll> , vector<pair<ll , ll>> , greater<pair<ll , ll>>>q; vector<pair<ll , ll>>adj[M]; vector<ll>graph[M] , top; bool vis[M]; inline void Dijkstra(int start) { q.push({0 , start}); while(q.size()) { int node = q.top().S; int cost = q.top().F; q.pop(); if(dis[type][node] || (node == start && cost)) continue; dis[type][node] = cost; for(auto next : adj[node]) q.push({cost + next.S , next.F}); } } inline void GetPath(int node) { vis[node] = 1; for(auto next : adj[node]) { int kid = next.F; if(dis[3][kid] + dis[4][kid] != dis[3][t] || vis[kid]) continue; graph[node].push_back(kid); graph[kid].push_back(node); ++cnt[node] , ++cnt[kid]; on[node] = 1; on[kid] = 1; GetPath(kid); } } inline void Bfs() { queue<ll>Q; Q.push(s); while(Q.size()) { int node = Q.front(); Q.pop(); top.push_back(node); for(auto next : graph[node]) { --cnt[next]; if(cnt[next] == 1) Q.push(next); } } top.push_back(t); } int main() { ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr); cin >> n >> m >> s >> t >> u >> v; for(int i = 1 ; i <= m ; ++i) { cin >> x >> y >> cost; adj[x].push_back({y , cost}); adj[y].push_back({x , cost}); } type = 1; Dijkstra(u); type = 2; Dijkstra(v); type = 3; Dijkstra(s); type = 4; Dijkstra(t); GetPath(s); Bfs(); for(int i = 1 ; i <= n ; ++i) U[i] = V[i] = 1e18; ans = dis[1][v]; for(auto node : top) { ans = min(ans , dis[1][node] + V[node]); ans = min(ans , dis[2][node] + U[node]); U[node] = min(U[node] , dis[1][node]); V[node] = min(V[node] , dis[2][node]); for(auto next : graph[node]) U[next] = min(U[next] , U[node]) , V[next] = min(V[next] , V[node]); } cout << ans << endl; 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...