제출 #667516

#제출 시각아이디문제언어결과실행 시간메모리
667516Reb007Commuter Pass (JOI18_commuter_pass)C++17
31 / 100
669 ms31732 KiB
// clang-format off #include <bits/stdc++.h> using namespace std; mt19937 rnd(time(0)); //#pragma GCC optimize("Ofast") //#pragma GCC optimize("fast-math") //#pragma GCC optimize("unroll-loops") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native") #define int long long #define ll long long #define ld long double #define sz(a) (int)a.size() #define all(a) a.begin(), a.end() const long long INF = 20000000000000000; const int inf = 1000000010; const int maxn = 262144; const int mxlg = 20; const double eps = 1e-13; int mod = 1e9 + 9; const int C = 340; vector<vector<pair<int, int>>> eds; int n; void dij(vector<vector<int>> &p, int s) { vector<int> dp(n, INF); dp[s] = 0; set<pair<int, int>> buf; buf.insert({0, s}); while (!buf.empty()) { int v = buf.begin()->second; buf.erase(buf.begin()); for (auto [to, c]: eds[v]) { if (dp[v] + c < dp[to]) { buf.erase({dp[to], to}); dp[to] = dp[v] + c; p[to].clear(); p[to].push_back(v); buf.insert({dp[to], to}); } else if (dp[v] + c == dp[to]) { p[to].push_back(v); } } } } vector<int> ans; void dij2(vector<vector<int>> &p, int s) { ans.assign(n, INF); ans[s] = 0; set<pair<int, int>> buf; buf.insert({0, s}); while (!buf.empty()) { int v = buf.begin()->second; buf.erase(buf.begin()); for (int to: p[v]) { if (ans[v] < ans[to]) { buf.erase({ans[to], to}); ans[to] = ans[v]; buf.insert({ans[to], to}); } } for (auto [to, c]: eds[v]) { if (ans[v] + c < ans[to]) { buf.erase({ans[to], to}); ans[to] = ans[v] + c; buf.insert({ans[to], to}); } } } } vector<int> buf; void del(vector<vector<int>> &p, int s, int t){ buf.push_back(s); vector<bool> used(n); used[s] = 1; while(!buf.empty()){ int v = buf.back(); buf.pop_back(); for(int to:p[v]){ if(!used[to]){ used[to] = 1; buf.push_back(to); } } } for (int i = 0; i < n; ++i) { if(!used[i])p[i].clear(); } } void solve() { int m, s, t, v, u; cin >> n >> m >> s >> t >> v >> u; --s, --t, --v, --u; eds.resize(n); for (int i = 0; i < m; ++i) { int x, y, c; cin >> x >> y >> c; --x, --y; eds[x].push_back({y, c}); eds[y].push_back({x, c}); } vector<vector<int>> st(n); vector<vector<int>> ts(n); dij(st, s); del(st, t, s); dij(ts, t); del(ts, s, t); int mn = INF; dij2(st, v); mn = min(mn, ans[u]); dij2(ts, v); mn = min(mn, ans[u]); cout << mn << '\n'; } signed main() { // freopen("kthzero.in", "r", stdin); // freopen("kthzero.out", "w", stdout); ios_base::sync_with_stdio(0); cin.tie(0); int __ = 1; // cin >> __; while (__--) 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...