제출 #1009281

#제출 시각아이디문제언어결과실행 시간메모리
1009281christinelynnCommuter Pass (JOI18_commuter_pass)C++17
15 / 100
2039 ms39340 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int INF = 1e18; struct DSU { vector<int> p, sz; vector<set<int>> children; DSU(int n) { p = vector<int>(n); children = vector<set<int>>(n, set<int>()); // mn = vector<int>(n); for(int i = 0; i < n; i++) { p[i] = i; children[i].insert(i); } } int find(int a) { if (a == p[a]) return p[a]; return p[a] = find(p[a]); } void join(int a, int b) { int r1 = find(a); int r2 = find(b); if (r1 == r2) return; p[r1] = r2; if (children[r1].size() > children[r2].size()) swap(children[r1], children[r2]); for (auto x : children[r1]) children[r2].insert(x); } }; void solve() { int n,m;cin>>n>>m; int s,t,u,v;cin>>s>>t>>u>>v;s--;t--;u--;v--; DSU dsu(n); vector<vector<pair<int, int>>> adj(n, vector<pair<int, int>>()); for (int i = 0; i < m; i++) { int u,v,w;cin>>u>>v>>w;u--;v--; adj[u].push_back({v, w}); adj[v].push_back({u, w}); } // djikstra from s priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int,int>>> pq; pq.push({0, s}); vector<int> dist(n, INF); while (!pq.empty()) { auto [cost, node] = pq.top();pq.pop(); if (cost > dist[node]) continue; dist[node] = cost; for (auto [children, w] : adj[node]) { if (cost+w < dist[children]) { dist[children] = cost+w; pq.push({cost+w, children}); } } } // mundur dari T, dan join vector<int> vis(n); function<void(int)> dfs = [&](int node) { vis[node] = 1; for (auto [children, w] : adj[node]) { if (dist[node] - w == dist[children]) { dfs(children); dsu.join(children, t); } } }; // for (auto el : dist) cout << el << " "; // cout << endl; dfs(t); // habis itu djikstra dari U -> V lagi vector<int> dp(n, INF); // pq.clear(); pq.push({0, u}); while (!pq.empty()) { auto [cost, node] = pq.top();pq.pop(); int r = dsu.find(node); if (cost > dp[r]) continue; dp[r] = cost; if (dsu.children[r].count(v)) { cout << cost << endl; return; } for (auto x : dsu.children[r]) { for (auto [children, w] : adj[x]) { if (cost+w < dp[dsu.find(children)]) { dp[children] = cost+w; pq.push({cost+w, dsu.find(children)}); } } } } // for (auto el : dp) cout << el << " "; } int32_t main() { ios_base::sync_with_stdio(0);cin.tie(0); int t=1; 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...