제출 #1092245

#제출 시각아이디문제언어결과실행 시간메모리
1092245fonikos01Commuter Pass (JOI18_commuter_pass)C++17
31 / 100
880 ms34112 KiB
#include <bits/stdc++.h> #include <vector> #include <tuple> // #include "debugging.h" // #include <atcoder/lazysegtree> // #include <atcoder/dsu> // #include <atcoder/segtree> // #include <atcoder/modint> // using namespace atcoder; // using mint = static_modint<998244353>; using namespace std; const int LARGE = 1e9; #define all(x) (x).begin(), (x).end() using ll = long long; typedef pair<ll, ll> pi; // bool cmp(pair<ll, ll> a, pair<ll, ll> b) // { // if (a.second < b.second) // return true; // return false; // } // struct node // { // // part which will store data // int data; // // pointer to the previous node // struct node *prev; // // pointer to the next node // struct node *next; // }; const int MOD = 998244353; // template<int MOD, int RT> struct mint { // static const int mod = MOD; // static constexpr mint rt() { return RT; } // primitive root // int v; // explicit operator int() const { return v; } // mint():v(0) {} // mint(ll _v):v(int(_v%MOD)) { v += (v<0)*MOD; } // mint& operator+=(mint o) { // if ((v += o.v) >= MOD) v -= MOD; // return *this; } // mint& operator-=(mint o) { // if ((v -= o.v) < 0) v += MOD; // return *this; } // mint& operator*=(mint o) { // v = int((ll)v*o.v%MOD); return *this; } // friend mint pow(mint a, ll p) { assert(p >= 0); // return p==0?1:pow(a*a,p/2)*(p&1?a:1); } // friend mint inv(mint a) { assert(a.v != 0); return pow(a,MOD-2); } // friend mint operator+(mint a, mint b) { return a += b; } // friend mint operator-(mint a, mint b) { return a -= b; } // friend mint operator*(mint a, mint b) { return a *= b; } // }; // using mi = mint<(int)MOD, 5>; mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count()); ll solve() { ll N, M; cin >> N >> M; ll s, t; cin >> s >> t;s--;t--; ll u, v; cin >> u >> v;u--;v--; vector<vector<pair<ll,ll>>> g(N, vector<pair<ll,ll>>(0)); for (int i = 0; i < M; i++) { ll a, b, c; cin >> a >> b >> c;a--;b--; g[a].push_back(make_pair(b, c)); g[b].push_back(make_pair(a, c)); } auto lol = [&](ll s, ll t, ll u, ll v) { vector<vector<ll>> nodePars(N, vector<ll>(0)); vector<ll> vis(N); priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq; pq.push(make_pair(0, s)); vector<ll> costToNode(N, INT64_MAX); while (!pq.empty()) { auto [cost, node] = pq.top(); pq.pop(); if (costToNode[node] == -1) continue; costToNode[node] = -1; for (auto [nei, c] : g[node]) { if (cost+c < costToNode[nei]) { costToNode[nei] = cost+c; nodePars[nei].clear(); nodePars[nei].push_back(node); } else if (cost+c == costToNode[nei]) nodePars[nei].push_back(node); pq.push(make_pair(cost+c, nei)); } } vector<ll> validNodes(N); vector<ll> st = {t}; while (!st.empty()) { ll node = st.back(); st.pop_back(); validNodes[node] = 1; for (auto par : nodePars[node]) { if (validNodes[par]) continue; st.push_back(par); } } for (int i = 0; i < N; i++) { if (validNodes[i] == 0) nodePars[i].clear(); } auto sol = [&](ll u, ll v) { vector<ll> spNodesToU(N, INT64_MAX); pq.push(make_pair(0, u)); while (!pq.empty()) { auto [cost, node] = pq.top(); pq.pop(); if (spNodesToU[node] != INT64_MAX) continue; spNodesToU[node] = cost; for (auto [nei, c] : g[node]) { pq.push(make_pair(cost+c, nei)); } } ll ans = INT64_MAX; vis.clear(); vis.resize(N, 0); pq.push(make_pair(0, v)); while (!pq.empty()) { auto [cost, node] = pq.top(); pq.pop(); if (vis[node]) continue; ans = min(ans, cost+spNodesToU[node]); vis[node] = 1; for (auto [nei, c] : g[node]) { pq.push(make_pair(cost+c, nei)); } for (auto par : nodePars[node]) { pq.push(make_pair(cost, par)); } } return ans; }; return min(sol(u, v), sol(v, u)); }; cout << min(lol(s, t, u, v), lol(t, s, u, v)) << '\n'; return 0; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); // freopen("mootube.in", "r", stdin); // freopen("mootube.out", "w", stdout); // ll caseCnt = 1; // ll T; // cin >> T; // while (T--) // { solve(); // cout << "Case #"<< caseCnt << ": " << ans << '\n'; // caseCnt++; // } 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...