Submission #862212

#TimeUsernameProblemLanguageResultExecution timeMemory
862212green_gold_dogCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
287 ms29248 KiB
//#pragma GCC optimize("Ofast") //#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,abm,popcnt,mmx") #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef double db; typedef long double ldb; typedef complex<double> cd; constexpr ll INF64 = 9'000'000'000'000'000'000, INF32 = 2'000'000'000, MOD = 1'000'000'007; constexpr db PI = acos(-1); constexpr bool IS_FILE = false, IS_TEST_CASES = false; random_device rd; mt19937 rnd32(rd()); mt19937_64 rnd64(rd()); template<typename T> bool assign_max(T& a, T b) { if (b > a) { a = b; return true; } return false; } template<typename T> bool assign_min(T& a, T b) { if (b < a) { a = b; return true; } return false; } template<typename T> T square(T a) { return a * a; } template<> struct std::hash<pair<ll, ll>> { ll operator() (pair<ll, ll> p) const { return ((__int128)p.first * MOD + p.second) % INF64; } }; vector<ll> dist(ll v, vector<vector<pair<ll, ll>>>& arr) { vector<ll> d(arr.size(), INF64); priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq; pq.emplace(0, v); d[v] = 0; while (!pq.empty()) { auto[nd, u] = pq.top(); pq.pop(); if (nd != d[u]) { continue; } for (auto[i, di] : arr[u]) { if (assign_min(d[i], nd + di)) { pq.emplace(d[i], i); } } } return d; } void dfs(ll v, vector<bool>& used, vector<vector<ll>>& tree, vector<ll>& ts) { used[v] = true; for (auto i : tree[v]) { if (!used[i]) { dfs(i, used, tree, ts); } } ts.push_back(v); } void solve() { ll n, m, s, t, u, v; cin >> n >> m >> s >> t >> u >> v; s--; t--; u--; v--; vector<vector<pair<ll, ll>>> arr(n); for (ll i = 0; i < m; i++) { ll a, b, c; cin >> a >> b >> c; a--; b--; arr[a].emplace_back(b, c); arr[b].emplace_back(a, c); } vector<ll> ds = dist(s, arr), dt = dist(t, arr), du = dist(u, arr), dv = dist(v, arr); ll dst = ds[t]; vector<vector<ll>> narr(n); for (ll i = 0; i < n; i++) { for (auto[j, c] : arr[i]) { if (ds[i] + c + dt[j] == dst) { narr[i].push_back(j); } } } vector<ll> ts; vector<bool> used(n, false); for (ll i = 0; i < n; i++) { if (!used[i]) { dfs(i, used, narr, ts); } } ll ans = du[v]; vector<ll> dp = du; for (auto i : ts) { for (auto j : narr[i]) { assign_min(dp[i], dp[j]); } assign_min(ans, dp[i] + dv[i]); } dp = dv; for (auto i : ts) { for (auto j : narr[i]) { assign_min(dp[i], dp[j]); } assign_min(ans, dp[i] + du[i]); } cout << ans << '\n'; } int main() { if (IS_FILE) { freopen("", "r", stdin); freopen("", "w", stdout); } ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); ll t = 1; if (IS_TEST_CASES) { cin >> t; } for (ll i = 0; i < t; i++) { solve(); } }

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:133:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |                 freopen("", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~
commuter_pass.cpp:134:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |                 freopen("", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...