제출 #887547

#제출 시각아이디문제언어결과실행 시간메모리
887547Perl32Commuter Pass (JOI18_commuter_pass)C++14
100 / 100
331 ms38600 KiB
// I wrote this code 4 u <3 #include <bits/stdc++.h> using namespace std; using ll = long long; #ifdef LOCAL #include "algo/debug.h" #else #define debug(...) 42 #endif const ll INFL = (ll) 1e18 + 1e9; signed main(int32_t argc, char *argv[]) { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m, s, t, su, sv; cin >> n >> m >> s >> t >> su >> sv; --s, --t, --su, --sv; vector<vector<pair<int, ll>>> g(n); for (int i = 0; i < m; ++i) { int u, v, w; cin >> u >> v >> w; --u, --v; g[u].emplace_back(v, w); g[v].emplace_back(u, w); } function<vector<ll>(int)> dijkstra = [&](int from) { set<pair<ll, int>> st; vector<ll> dist(n, INFL); dist[from] = 0ll; st.insert({0ll, from}); while (!st.empty()) { int u = st.begin()->second; st.erase(st.begin()); for (auto [to, w] : g[u]) { if (dist[to] > dist[u] + w) { st.erase({dist[to], to}); dist[to] = dist[u] + w; st.insert({dist[to], to}); } } } return dist; }; vector<ll> distS = dijkstra(s); vector<bool> used(n, false), can(n, false); can[t] = true; vector<vector<int>> dag(n); function<void(int)> Dfs1 = [&](int u) { used[u] = true; for (auto [to, w] : g[u]) { if (distS[to] != distS[u] + w) continue; if (!used[to]) Dfs1(to); can[u] = can[u] || can[to]; if (can[to]) { dag[u].emplace_back(to); } } }; Dfs1(s); fill(used.begin(), used.end(), false); vector<ll> distV = dijkstra(sv), distU = dijkstra(su), closeV(n, INFL), closeU(n, INFL);; function<void(int)> Dfs2 = [&](int u) { used[u] = true; closeV[u] = distV[u]; closeU[u] = distU[u]; for (auto to : dag[u]) { if (!used[to]) Dfs2(to); closeV[u] = min(closeV[u], closeV[to]); closeU[u] = min(closeU[u], closeU[to]); } }; Dfs2(s); ll ans = distU[sv]; for (int i = 0; i < n; ++i) { ans = min({ans, closeV[i] + distU[i], closeU[i] + distV[i]}); } cout << ans; } /* */

컴파일 시 표준 에러 (stderr) 메시지

commuter_pass.cpp: In lambda function:
commuter_pass.cpp:38:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |             for (auto [to, w] : g[u]) {
      |                       ^
commuter_pass.cpp: In lambda function:
commuter_pass.cpp:54:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   54 |         for (auto [to, w] : g[u]) {
      |                   ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...