제출 #963797

#제출 시각아이디문제언어결과실행 시간메모리
963797raspyCommuter Pass (JOI18_commuter_pass)C++14
15 / 100
2069 ms29528 KiB
#include <iostream> #include <vector> #include <queue> #include <tuple> #include <unordered_set> #include <cstring> #define inf 1'000'000'000'000 #define int long long using namespace std; typedef pair<int, int> ii; vector<pair<int, int>> graf[100005]; vector<int> par[100005]; pair<int, int> dp[100005]; void dij(int st, vector<int>& dist, bool dg = false) { priority_queue<ii, vector<ii>, greater<ii>> pq; pq.push({0, st}); dist[st] = 0; while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (d > dist[u]) continue; for (auto [v, w] : graf[u]) { if (dist[v] != -1 && d+w > dist[v]) continue; if (dg) { if (d+w == dist[v]) { par[v].push_back(u); continue; } par[v].clear(); par[v].push_back(u); // cout << u << "->" << v << "\n"; } else if (d+w == dist[v]) continue; dist[v] = d+w; pq.push({dist[v], v}); } } } int gl = 0; pair<int, int> dfs(vector<int>& dist1, vector<int>& dist2, int vz) { if (dp[vz].first != 0) return dp[vz]; pair<int, int> rez = {dist1[vz], dist2[vz]}; for (int v : par[vz]) { gl++; auto[nu, nv] = dfs(dist1, dist2, v); gl--; if (nu < rez.first) { rez.first = nu; rez.second = min(dist2[vz], nv); } else if (nv < rez.second) { rez.second = nv; rez.first = min(dist1[vz], nu); } } return dp[vz] = rez; } int32_t main() { int n, m; cin >> n >> m; int s, t; cin >> s >> t; int u, v; cin >> u >> v; for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; graf[u].push_back({v, w}); graf[v].push_back({u, w}); } vector<int> dist2(n+1, -1); vector<int> dist3(n+1, -1); dij(s, dist2, true); fill(dist2.begin(), dist2.end(), -1); dij(u, dist2); dij(v, dist3); int rez = dist2[v]; pair<int, int> par = dfs(dist2, dist3, t); cout << min(rez, par.first+par.second) << "\n"; // for (int i = 1; i <= n; i++) // cout << dp[i].first << " " << dp[i].second << "\n"; return 0; }

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

commuter_pass.cpp: In function 'void dij(long long int, std::vector<long long int>&, bool)':
commuter_pass.cpp:25:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   25 |   auto [d, u] = pq.top();
      |        ^
commuter_pass.cpp:29:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   29 |   for (auto [v, w] : graf[u])
      |             ^
commuter_pass.cpp: In function 'std::pair<long long int, long long int> dfs(std::vector<long long int>&, std::vector<long long int>&, long long int)':
commuter_pass.cpp:61:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |   auto[nu, nv] = dfs(dist1, dist2, v);
      |       ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...