제출 #944254

#제출 시각아이디문제언어결과실행 시간메모리
944254tnknguyen_Commuter Pass (JOI18_commuter_pass)C++14
100 / 100
280 ms34012 KiB
#include <bits/stdc++.h> using namespace std; #define endl '\n' #define pll pair<long long, long long> const int sz = 1e5 + 5; vector<pll> gr[sz]; long long d[5][sz]; long long f[5][sz]; int n, m, S, T, U, V; //constants long long ST; long long UV; void Dijkstra(int k, int s){ priority_queue<pll> q; d[k][s] = 0; q.push({0, s}); while(q.size()){ long long w, u; tie(w, u) = q.top(); w = -w; q.pop(); if(w > d[k][u]){ continue; } for(pll p : gr[u]){ long long v, c; tie(v, c) = p; if(w + c < d[k][v]){ d[k][v] = w + c; q.push({-d[k][v], v}); } } } } vector<int> dag[sz]; int vi[sz]; void build_DAG(int v){ vi[v] = 1; for(pll p : gr[v]){ long long u, c; tie(u, c) = p; if(d[0][u] + c + d[1][v] == ST){ dag[u].push_back(v); if(vi[u] == 0){ build_DAG(u); } } } } deque<int> tp; void topo(int u){ vi[u] = 2; for(int v : dag[u]){ if(vi[v] != 2){ topo(v); } } tp.push_front(u); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("main.inp","r",stdin); // freopen("main.out","w",stdout); cin >> n >> m; cin >> S >> T; cin >> U >> V; while(m--){ int u, v, c; cin>>u>>v>>c; gr[u].push_back({v, c}); gr[v].push_back({u, c}); } memset(d, 63, sizeof(d)); Dijkstra(0, S); Dijkstra(1, T); Dijkstra(2, U); Dijkstra(3, V); ST = d[0][T]; UV = d[2][V]; build_DAG(T); topo(S); for(int i=1;i<=n;++i){ f[0][i] = d[2][i]; // U -> i f[1][i] = d[3][i]; // V -> i } for(int u : tp){ for(int v : dag[u]){ f[0][v] = min(f[0][v], f[0][u]); f[1][v] = min(f[1][v], f[1][u]); } } long long ans = UV; for(int i=1;i<=n;++i){ if(d[0][i] + d[1][i] == ST){ ans = min({ans, f[0][i] + d[3][i], f[1][i] + d[2][i]}); } } 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...