제출 #575414

#제출 시각아이디문제언어결과실행 시간메모리
575414_karan_gandhiCommuter Pass (JOI18_commuter_pass)C++17
15 / 100
2076 ms26344 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define all(v) v.begin(), v.end() #define endl '\n' #define pl(var) " [" << #var << ": " << (var) << "] " template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "[" << p.first << ", " << p.second << "]"; } template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) { cout << "["; for(ll int i = 0; i < (ll int)v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";} ll int inf = 1e18; vector<ll int> distancesS, distancesU, distancesV, distances; vector<vector<pair<ll int, ll int>>> adj; vector<vector<ll int>> from, to; void djkstra(ll int start) { fill(all(distances), inf); distances[start] = 0; priority_queue<pair<ll int, ll int>> pq; pq.emplace(0, start); while (pq.size()) { ll int node, d; tie(d, node) = pq.top(); pq.pop(); d = -1 * d; if (distances[node] != d) continue; for (auto [v, wt] : adj[node]) { ll int new_dist = d + wt; if (new_dist < distances[v]) { distances[v] = new_dist; pq.emplace(-new_dist, v); } } } } void dfs1(ll int u) { // use from and build to for (ll int v : from[u]) { to[v].push_back(u); dfs1(v); } } ll int ans = 0; ll int dfs2(ll int u) { ll int mn = inf; for (ll int v : from[u]) { mn = min(mn, dfs2(v)); } ans = min(ans, mn + distancesV[u]); return min(mn, distancesU[u]); } void solve() { ll int n, m; cin >> n >> m; ll int s, t; cin >> s >> t; s--, t--; ll int U, V; cin >> U >> V; U--, V--; adj.resize(n); distances.resize(n); distancesS.resize(n); distancesU.resize(n); distancesV.resize(n); from.resize(n); for (ll int i = 0; i < m; i++) { ll int a, b, c; cin >> a >> b >> c; a--, b--; adj[a].emplace_back(b, c); adj[b].emplace_back(a, c); } // run djkstra djkstra(U); for (ll int i = 0; i < n; i++) distancesU[i] = distances[i]; djkstra(V); for (ll int i = 0; i < n; i++) distancesV[i] = distances[i]; auto djkstra1 = [&]() { // I know u and v fill(all(distancesS), inf); distancesS[s] = 0; priority_queue<pair<ll int, ll int>> pq; pq.emplace(0, s); while (pq.size()) { auto [dist, node] = pq.top(); pq.pop(); dist = dist * -1; if (distancesS[node] != dist) continue; for (auto [v, wt] : adj[node]) { ll int new_dist = dist + wt; if (new_dist < distancesS[v]) { distancesS[v] = new_dist; from[v].clear(); from[v].push_back(node); pq.emplace(-new_dist, v); } else if (new_dist == distancesS[v]) { from[v].push_back(node); } } } // dfs1(t); }; // cout << pl(distances) djkstra1(); ans = distancesU[V]; // assert(distancesS[V] == distancesV[U]); dfs2(t); // change s and v and run dfs2 again distancesV.swap(distancesU); dfs2(t); cout << ans << endl; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll int T = 1; // cin >> T; while (T--) solve(); 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...