Submission #1180641

#TimeUsernameProblemLanguageResultExecution timeMemory
1180641blackslexCommuter Pass (JOI18_commuter_pass)C++17
15 / 100
331 ms20468 KiB
#include<bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<ll, ll>; int n, m, s, t, uu, vv, x, y, z; int main() { scanf("%d %d %d %d %d %d", &n, &m, &s, &t, &uu, &vv); vector<vector<pii>> v(n + 5, vector<pii>()); vector<ll> d(n + 5, 1e18), d2(n + 5, 1e18); ll ans = 1e18; for (int i = 0; i < m; i++) { scanf("%d %d %d", &x, &y, &z); v[x].emplace_back(y, z); v[y].emplace_back(x, z); } auto dijk = [&] (int st, vector<ll> &dist) { priority_queue<pii, vector<pii>, greater<pii>> pq; pq.emplace(dist[st] = 0, st); while (!pq.empty()) { auto [nd, nn] = pq.top(); pq.pop(); for (auto &[tn, td]: v[nn]) { if (dist[tn] > dist[nn] + td) pq.emplace(dist[tn] = dist[nn] + td, tn); } } }; auto dijk2 = [&] (int st, int ed) { priority_queue<pii, vector<pii>, greater<pii>> pq; vector<ll> dist(n + 5, 1e18); vector<vector<ll>> dp(2, vector<ll>(n + 5, 1e18)); pq.emplace(dist[st] = 0, st); while (!pq.empty()) { auto [nd, nn] = pq.top(); pq.pop(); for (auto &[tn, td]: v[nn]) { ll xx0 = min(dp[0][nn], d[tn]), xx1 = min(dp[1][nn], d2[tn]); if (dist[tn] > dist[nn] + td) { dp[0][tn] = xx0; dp[1][tn] = xx1; pq.emplace(dist[tn] = dist[nn] + td, tn); } else if (dist[tn] == dist[tn] + td && xx0 + xx1 <= dp[0][tn] + dp[1][tn]) { dp[0][tn] = xx0; dp[1][tn] = xx1; } } } ans = min(ans, dp[0][ed] + dp[1][ed]); }; dijk(uu, d); dijk(vv, d2); ans = min(ans, d[vv]); dijk2(s, t); dijk2(t, s); printf("%lld", ans); }

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:10:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |     scanf("%d %d %d %d %d %d", &n, &m, &s, &t, &uu, &vv);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:15:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |         scanf("%d %d %d", &x, &y, &z);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...