제출 #857596

#제출 시각아이디문제언어결과실행 시간메모리
857596dio_2Commuter Pass (JOI18_commuter_pass)C++17
31 / 100
2031 ms15984 KiB
#include<bits/stdc++.h> using namespace std; const long long inf = (long long)1e18; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, s, t, u, v; cin >> n >> m >> s >> t >> u >> v; vector<vector<pair<int, int>>> adj(n + 1); while(m--){ int a, b, c; cin >> a >> b >> c; adj[a].emplace_back(b, c); adj[b].emplace_back(a, c); } auto Do = [&](int src, vector<long long> &d)->void{ fill(d.begin(), d.end(), inf); vector<bool> in_Q(n + 1); d[src] = 0; priority_queue<pair<long long, int>> pq; pq.push({0, src}); while(!pq.empty()){ auto [_, node] = pq.top(); pq.pop(); if(in_Q[node]) continue; in_Q[node] = 1; for(auto [to, cost] : adj[node]){ if(d[node] + cost < d[to]){ d[to] = d[node] + cost; pq.push({-d[to], to}); } } } }; auto clear_cost = [&](int a, int b)->void{ for(auto &[node, _] : adj[a]) if(node == b) _ = 0; for(auto &[node, _] : adj[b]) if(node == a) _ = 0; }; auto in_path = [&](int a, int b)->bool{ vector<long long> Da(n + 1); vector<long long> Db(n + 1); Do(a, Da); Do(b, Db); return (Da[t] == Da[b] + Db[t]); }; vector<long long> Ds(n + 1); vector<bool> in_sp(n + 1); Do(s, Ds); bool unique = 1; queue<int> q; q.push(t); in_sp[t] = 1; vector<pair<int, int>> combs; while(!q.empty()){ int node = q.front(); q.pop(); int cnt = 0; for(auto [from, cost] : adj[node]){ if(Ds[from] + cost == Ds[node] && !in_sp[from]){ in_sp[from] = 1; q.push(from); ++cnt; unique &= (cnt == 1); combs.emplace_back(from, node); } } } if(unique){ for(auto [a, b] : combs) clear_cost(a, b); } vector<long long> Du(n + 1), Dv(n + 1); Do(u, Du); Do(v, Dv); if(unique){ cout << Du[v] << '\n'; return 0; } if(s == u){ long long ans = inf; for(int i = 1;i <= n;i++) if(in_sp[i]) ans = min(ans, Dv[i]); cout << ans << '\n'; return 0; } long long ans = Du[v]; if(n <= 300){ for(int i = 1;i <= n;i++){ for(int j = 1;j <= n;j++){ if(!in_sp[i] || !in_sp[j]) continue; if(in_path(i, j)){ ans = min(ans, Du[i] + Dv[j]); ans = min(ans, Dv[i] + Du[j]); } } } } 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...