Submission #678589

#TimeUsernameProblemLanguageResultExecution timeMemory
678589jahsdwaijsdCommuter Pass (JOI18_commuter_pass)C++14
Compilation error
0 ms0 KiB
/* #pragma GCC optimize("Ofast") #pragma GCC target("avx2") #pragma GCC optimize("unroll-loops") */ #include <bits/stdc++.h> #define taskname "bai3" #define all(x) x.begin(), x.end() #define ll long long #define ull unsigned ll #define ld long double #define pb push_back #define ff first #define ss second #define pii pair<int, int> #define pll pair<ll, ll> #define vi vector<int> using namespace std; using cd = complex<double>; const int mxN = 1e5 + 5; const int mod = 1e9 + 7; const ll oo = 1e18; int n, m, s, t, u, v; ll dp[mxN][2][2]; vector<ll> from_u, from_v; vector<pair<int, ll>> G[mxN]; vector<ll> dijkstra(int v) { vector<ll> res(n + 1, oo); vector<bool> vis(n + 1); res[v] = 0; priority_queue<pair<ll, int>> pq; pq.push({0, v}); while(pq.size()) { pair<ll, int> top = pq.top(); pq.pop(); if(vis[top.ss]) continue; vis[top.ss] = true; for(auto [u, w] : G[top.ss]) { if(res[u] > res[top.ss] + w) { res[u] = res[top.ss] + w; pq.push({-res[u], u}); } } } return res; } void dijkstra1(int s, int t) { vector<ll> res(n + 1, oo); for(int i = 1; i <= n; ++i) dp[i][0][0] = dp[i][0][1] = dp[i][1][0] = dp[i][1][1] = oo; vector<bool> vis(n + 1); priority_queue<pair<ll, int>> pq; res[s] = 0; dp[s][0][0] = 0; dp[s][0][1] = from_v[s]; dp[s][1][0] = from_u[s]; dp[s][1][1] = from_v[s] + from_u[s]; pq.push({0, s}); while(pq.size()) { pair<ll, int> top = pq.top(); pq.pop(); if(vis[top.ss]) continue; vis[top.ss] = true; for(auto [u, w] : G[top.ss]) { if(res[u] > res[top.ss] + w) { res[u] = res[top.ss] + w; pq.push({-res[u], u}); dp[u][0][1] = min(dp[top.ss][0][1], from_v[u]); dp[u][1][0] = min(dp[top.ss][1][0], from_u[u]); dp[u][1][1] = min(dp[top.ss][1][1], dp[top.ss][0][1] + from_u[u], dp[top.ss][1][0] + from_v[u], from_v[u] + from_u[u]); } else if(res[u] == res[top.ss] + w) { dp[u][0][1] = min({dp[u][0][1], dp[top.ss][0][1], from_v[u]}); dp[u][1][0] = min({dp[u][1][0], dp[top.ss][1][0], from_u[u]}); dp[u][1][1] = min({dp[u][1][1], dp[top.ss][1][1], dp[top.ss][0][1] + from_u[u], dp[top.ss][1][0] + from_v[u], from_v[u] + from_u[u]}); } } } cout << min(from_u[v], dp[t][1][1]) << "\n"; } void solve() { cin >> n >> m; cin >> s >> t >> u >> v; for(int i = 1; i <= m; ++i) { int u, v, w; cin >> u >> v >> w; G[u].pb({v, w}); G[v].pb({u, w}); } from_u = dijkstra(u); from_v = dijkstra(v); dijkstra1(s, t); } signed main() { #ifdef CDuongg freopen("bai3.inp", "r", stdin); freopen("bai3.out", "w", stdout); auto start = chrono::high_resolution_clock::now(); #endif ios_base::sync_with_stdio(false); cin.tie(nullptr); int t = 1; //cin >> t; while(t--) solve(); #ifdef CDuongg auto end = chrono::high_resolution_clock::now(); cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '='; cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl; #endif }

Compilation message (stderr)

commuter_pass.cpp: In function 'std::vector<long long int> dijkstra(int)':
commuter_pass.cpp:41:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |         for(auto [u, w] : G[top.ss]) {
      |                  ^
commuter_pass.cpp: In function 'void dijkstra1(int, int)':
commuter_pass.cpp:69:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |         for(auto [u, w] : G[top.ss]) {
      |                  ^
commuter_pass.cpp:75:134: error: no matching function for call to 'min(long long int&, long long int, long long int, __gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type)'
   75 |                 dp[u][1][1] = min(dp[top.ss][1][1], dp[top.ss][0][1] + from_u[u], dp[top.ss][1][0] + from_v[u], from_v[u] + from_u[u]);
      |                                                                                                                                      ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from commuter_pass.cpp:6:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
commuter_pass.cpp:75:134: note:   candidate expects 2 arguments, 4 provided
   75 |                 dp[u][1][1] = min(dp[top.ss][1][1], dp[top.ss][0][1] + from_u[u], dp[top.ss][1][0] + from_v[u], from_v[u] + from_u[u]);
      |                                                                                                                                      ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from commuter_pass.cpp:6:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
commuter_pass.cpp:75:134: note:   candidate expects 3 arguments, 4 provided
   75 |                 dp[u][1][1] = min(dp[top.ss][1][1], dp[top.ss][0][1] + from_u[u], dp[top.ss][1][0] + from_v[u], from_v[u] + from_u[u]);
      |                                                                                                                                      ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from commuter_pass.cpp:6:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3468 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note:   template argument deduction/substitution failed:
commuter_pass.cpp:75:134: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   75 |                 dp[u][1][1] = min(dp[top.ss][1][1], dp[top.ss][0][1] + from_u[u], dp[top.ss][1][0] + from_v[u], from_v[u] + from_u[u]);
      |                                                                                                                                      ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from commuter_pass.cpp:6:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3474 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note:   template argument deduction/substitution failed:
commuter_pass.cpp:75:134: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   75 |                 dp[u][1][1] = min(dp[top.ss][1][1], dp[top.ss][0][1] + from_u[u], dp[top.ss][1][0] + from_v[u], from_v[u] + from_u[u]);
      |                                                                                                                                      ^