# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
956245 | 2024-04-01T11:55:21 Z | samvar_0907 | Olympic Bus (JOI20_ho_t4) | C++17 | Compilation error |
0 ms | 0 KB |
#include<bits/stdc++.h> using namespace std; #define int long long const int N = 201, M = 40001; int n, m; multiset<pair<int, int>> adj[N]; int c[M], d[M]; pair<int, int> edges[M]; vector<int> dijkstra(int source){ vector<int> dist(n + 1, 1e15); priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; pq.push({0, source}); dist[source] = 0; while (!pq.empty()) { int u = pq.top().second; int d = pq.top().first; pq.pop(); for (auto &n : adj[u]){ if (dist[n.first] > d + c[n.second]){ dist[n.first] = d + c[n.second]; pq.push({dist[n.first], n.first}); } } } return dist; } signed main(){ cin >> n >> m; for (int i = 1; i <= n; ++i) { adj[i].clear(); } vector<vector<int>> dist(n + 1, vector<int>(n + 1, 1e15)); for (int i = 1; i <= n; ++i) { dist[i][i] = 0; } for (int i = 0; i < m; ++i){ int u, v; cin >> u >> v >> c[i] >> d[i]; adj[u].insert({v, i}); edges[i] = {u, v}; dist[u][v] = min(dist[u][v], c[i]); } // Floyd Warshall for (int k = 1; k <= n; ++k) { for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); } } } int ans = min(dist[1][n] + dist[n][1]); int u = edges[i].first, v = edges[i].second; if (min(dist[1][n], dist[1][v] + c[i] + dist[u][n]) + min(dist[n][1], dist[n][v] + c[i] + dist[u][1]) + d[i] < ans) { adj[u].erase(adj[u].find({v, i})); adj[v].insert({u, i}); ans = min(ans, d[i] + dijkstra(1)[n] + dijkstra(n)[1]); adj[v].erase(adj[v].find({edges[i].first, i})); adj[u].insert({v, i}); } if (ans == (int)(1e15)) { ans = -1; } cout << ans; }
Compilation message
ho_t4.cpp: In function 'int main()': ho_t4.cpp:60:42: error: no matching function for call to 'min(__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type)' 60 | int ans = min(dist[1][n] + dist[n][1]); | ^ In file included from /usr/include/c++/10/bits/specfun.h:45, from /usr/include/c++/10/cmath:1927, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41, from ho_t4.cpp:1: /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: ho_t4.cpp:60:42: note: candidate expects 2 arguments, 1 provided 60 | int ans = min(dist[1][n] + dist[n][1]); | ^ In file included from /usr/include/c++/10/bits/specfun.h:45, from /usr/include/c++/10/cmath:1927, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41, from ho_t4.cpp:1: /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: ho_t4.cpp:60:42: note: candidate expects 3 arguments, 1 provided 60 | int ans = min(dist[1][n] + dist[n][1]); | ^ In file included from /usr/include/c++/10/algorithm:62, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65, from ho_t4.cpp:1: /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: ho_t4.cpp:60:42: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int' 60 | int ans = min(dist[1][n] + dist[n][1]); | ^ In file included from /usr/include/c++/10/algorithm:62, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65, from ho_t4.cpp:1: /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: ho_t4.cpp:60:42: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int' 60 | int ans = min(dist[1][n] + dist[n][1]); | ^ ho_t4.cpp:61:19: error: 'i' was not declared in this scope 61 | int u = edges[i].first, v = edges[i].second; | ^ ho_t4.cpp:63:33: error: 'v' was not declared in this scope 63 | if (min(dist[1][n], dist[1][v] + c[i] + dist[u][n]) + | ^ ho_t4.cpp:66:44: error: no matching function for call to 'std::multiset<std::pair<long long int, long long int> >::find(<brace-enclosed initializer list>)' 66 | adj[u].erase(adj[u].find({v, i})); | ^ In file included from /usr/include/c++/10/set:62, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:87, from ho_t4.cpp:1: /usr/include/c++/10/bits/stl_multiset.h:775:7: note: candidate: 'std::multiset<_Key, _Compare, _Alloc>::iterator std::multiset<_Key, _Compare, _Alloc>::find(const key_type&) [with _Key = std::pair<long long int, long long int>; _Compare = std::less<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<long long int, long long int> >; std::multiset<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::_Identity<std::pair<long long int, long long int> >, std::less<std::pair<long long int, long long int> >, std::allocator<std::pair<long long int, long long int> > >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::key_type = std::pair<long long int, long long int>]' 775 | find(const key_type& __x) | ^~~~ /usr/include/c++/10/bits/stl_multiset.h:775:28: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const key_type&' {aka 'const std::pair<long long int, long long int>&'} 775 | find(const key_type& __x) | ~~~~~~~~~~~~~~~~^~~ /usr/include/c++/10/bits/stl_multiset.h:779:7: note: candidate: 'std::multiset<_Key, _Compare, _Alloc>::const_iterator std::multiset<_Key, _Compare, _Alloc>::find(const key_type&) const [with _Key = std::pair<long long int, long long int>; _Compare = std::less<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<long long int, long long int> >; std::multiset<_Key, _Compare, _Alloc>::const_iterator = std::_Rb_tree<std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::_Identity<std::pair<long long int, long long int> >, std::less<std::pair<long long int, long long int> >, std::allocator<std::pair<long long int, long long int> > >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::key_type = std::pair<long long int, long long int>]' 779 | find(const key_type& __x) const | ^~~~ /usr/include/c++/10/bits/stl_multiset.h:779:28: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const key_type&' {aka 'const std::pair<long long int, long long int>&'} 779 | find(const key_type& __x) const | ~~~~~~~~~~~~~~~~^~~ /usr/include/c++/10/bits/stl_multiset.h:785:2: note: candidate: 'template<class _Kt> decltype (std::multiset<_Key, _Compare, _Alloc>::iterator{((std::multiset<_Key, _Compare, _Alloc>*)this)->std::multiset<_Key, _Compare, _Alloc>::_M_t._M_find_tr(__x)}) std::multiset<_Key, _Compare, _Alloc>::find(const _Kt&) [with _Kt = _Kt; _Key = std::pair<long long int, long long int>; _Compare = std::less<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<long long int, long long int> >]' 785 | find(const _Kt& __x) | ^~~~ /usr/include/c++/10/bits/stl_multiset.h:785:2: note: template argument deduction/substitution failed: ho_t4.cpp:66:44: note: couldn't deduce template parameter '_Kt' 66 | adj[u].erase(adj[u].find({v, i})); | ^ In file included from /usr/include/c++/10/set:62, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:87, from ho_t4.cpp:1: /usr/include/c++/10/bits/stl_multiset.h:791:2: note: candidate: 'template<class _Kt> decltype (std::multiset<_Key, _Compare, _Alloc>::const_iterator{((const std::multiset<_Key, _Compare, _Alloc>*)this)->std::multiset<_Key, _Compare, _Alloc>::_M_t._M_find_tr(__x)}) std::multiset<_Key, _Compare, _Alloc>::find(const _Kt&) const [with _Kt = _Kt; _Key = std::pair<long long int, long long int>; _Compare = std::less<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<long long int, long long int> >]' 791 | find(const _Kt& __x) const | ^~~~ /usr/include/c++/10/bits/stl_multiset.h:791:2: note: template argument deduction/substitution failed: ho_t4.cpp:66:44: note: couldn't deduce template parameter '_Kt' 66 | adj[u].erase(adj[u].find({v, i})); | ^ ho_t4.cpp:70:33: error: no matching function for call to 'std::multiset<std::pair<long long int, long long int> >::insert(<brace-enclosed initializer list>)' 70 | adj[u].insert({v, i}); | ^ In file included from /usr/include/c++/10/set:62, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:87, from ho_t4.cpp:1: /usr/include/c++/10/bits/stl_multiset.h:502:7: note: candidate: 'std::multiset<_Key, _Compare, _Alloc>::iterator std::multiset<_Key, _Compare, _Alloc>::insert(const value_type&) [with _Key = std::pair<long long int, long long int>; _Compare = std::less<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<long long int, long long int> >; std::multiset<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::_Identity<std::pair<long long int, long long int> >, std::less<std::pair<long long int, long long int> >, std::allocator<std::pair<long long int, long long int> > >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::value_type = std::pair<long long int, long long int>]' 502 | insert(const value_type& __x) | ^~~~~~ /usr/include/c++/10/bits/stl_multiset.h:502:32: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const std::pair<long long int, long long int>&'} 502 | insert(const value_type& __x) | ~~~~~~~~~~~~~~~~~~^~~ /usr/include/c++/10/bits/stl_multiset.h:507:7: note: candidate: 'std::multiset<_Key, _Compare, _Alloc>::iterator std::multiset<_Key, _Compare, _Alloc>::insert(std::multiset<_Key, _Compare, _Alloc>::value_type&&) [with _Key = std::pair<long long int, long long int>; _Compare = std::less<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<long long int, long long int> >; std::multiset<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::_Identity<std::pair<long long int, long long int> >, std::less<std::pair<long long int, long long int> >, std::allocator<std::pair<long long int, long long int> > >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::value_type = std::pair<long long int, long long int>]' 507 | insert(value_type&& __x) | ^~~~~~ /usr/include/c++/10/bits/stl_multiset.h:507:27: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::multiset<std::pair<long long int, long long int> >::value_type&&' {aka 'std::pair<long long int, long long int>&&'} 507 | insert(value_type&& __x) | ~~~~~~~~~~~~~^~~ /usr/include/c++/10/bits/stl_multiset.h:532:7: note: candidate: 'std::multiset<_Key, _Compare, _Alloc>::iterator std::multiset<_Key, _Compare, _Alloc>::insert(std::multiset<_Key, _Compare, _Alloc>::const_iterator, const value_type&) [with _Key = std::pair<long long int, long long int>; _Compare = std::less<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<long long int, long long int> >; std::multiset<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::_Identity<std::pair<long long int, long long int> >, std::less<std::pair<long long int, long long int> >, std::allocator<std::pair<long long int, long long int> > >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::const_iterator = std::_Rb_tree<std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::_Identity<std::pair<long long int, long long int> >, std::less<std::pair<long long int, long long int> >, std::allocator<std::pair<long long int, long long int> > >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::value_type = std::pair<long long int, long long int>]' 532 | insert(const_iterator __position, const value_type& __x) | ^~~~~~ /usr/include/c++/10/bits/stl_multiset.h:532:7: note: candidate expects 2 arguments, 1 provided /usr/include/c++/10/bits/stl_multiset.h:537:7: note: candidate: 'std::multiset<_Key, _Compare, _Alloc>::iterator std::multiset<_Key, _Compare, _Alloc>::insert(std::multiset<_Key, _Compare, _Alloc>::const_iterator, std::multiset<_Key, _Compare, _Alloc>::value_type&&) [with _Key = std::pair<long long int, long long int>; _Compare = std::less<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<long long int, long long int> >; std::multiset<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::_Identity<std::pair<long long int, long long int> >, std::less<std::pair<long long int, long long int> >, std::allocator<std::pair<long long int, long long int> > >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::const_iterator = std::_Rb_tree<std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::_Identity<std::pair<long long int, long long int> >, std::less<std::pair<long long int, long long int> >, std::allocator<std::pair<long long int, long long int> > >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::value_type = std::pair<long long int, long long int>]' 537 | insert(const_iterator __position, value_type&& __x) | ^~~~~~ /usr/include/c++/10/bits/stl_multiset.h:537:7: note: candidate expects 2 arguments, 1 provided /usr/include/c++/10/bits/stl_multiset.h:551:2: note: candidate: 'template<class _InputIterator> void std::multiset<_Key, _Compare, _Alloc>::insert(_InputIterator, _InputIterator) [with _InputIterator = _InputIterator; _Key = std::pair<long long int, long long int>; _Compare = std::less<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<long long int, long long int> >]' 551 | insert(_InputIterator __first, _InputIterator __last) | ^~~~~~ /usr/include/c++/10/bits/stl_multiset.h:551:2: note: template argument deduction/substitution failed: ho_t4.cpp:70:33: note: candidate expects 2 arguments, 1 provided 70 | adj[u].insert({v, i}); | ^ In file included from /usr/include/c++/10/set:62, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:87, from ho_t4.cpp:1: /usr/include/c++/10/bits/stl_multiset.h:563:7: note: candidate: 'void std::multiset<_Key, _Compare, _Alloc>::insert(std::initializer_list<_Tp>) [with _Key = std::pair<long long int, long long int>; _Compare = std::less<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<long long int, long long int> >]' 563 | insert(initializer_list<value_type> __l) | ^~~~~~ /usr/include/c++/10/bits/stl_multiset.h:563:43: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::initializer_list<std::pair<long long int, long long int> >' 563 | insert(initializer_list<value_type> __l) | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~ /usr/include/c++/10/bits/stl_multiset.h:583:7: note: candidate: 'std::multiset<_Key, _Compare, _Alloc>::iterator std::multiset<_Key, _Compare, _Alloc>::insert(std::multiset<_Key, _Compare, _Alloc>::node_type&&) [with _Key = std::pair<long long int, long long int>; _Compare = std::less<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<long long int, long long int> >; std::multiset<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::_Identity<std::pair<long long int, long long int> >, std::less<std::pair<long long int, long long int> >, std::allocator<std::pair<long long int, long long int> > >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::node_type = std::_Rb_tree<std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::_Identity<std::pair<long long int, long long int> >, std::less<std::pair<long long int, long long int> >, std::allocator<std::pair<long long int, long long int> > >::node_type]' 583 | insert(node_type&& __nh) | ^~~~~~ /usr/include/c++/10/bits/stl_multiset.h:583:26: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::multiset<std::pair<long long int, long long int> >::node_type&&' {aka 'std::_Rb_tree<std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::_Identity<std::pair<long long int, long long int> >, std::less<std::pair<long long int, long long int> >, std::allocator<std::pair<long long int, long long int> > >::node_type&&'} 583 | insert(node_type&& __nh) | ~~~~~~~~~~~~^~~~ /usr/include/c++/10/bits/stl_multiset.h:588:7: note: candidate: 'std::multiset<_Key, _Compare, _Alloc>::iterator std::multiset<_Key, _Compare, _Alloc>::insert(std::multiset<_Key, _Compare, _Alloc>::const_iterator, std::multiset<_Key, _Compare, _Alloc>::node_type&&) [with _Key = std::pair<long long int, long long int>; _Compare = std::less<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<long long int, long long int> >; std::multiset<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::_Identity<std::pair<long long int, long long int> >, std::less<std::pair<long long int, long long int> >, std::allocator<std::pair<long long int, long long int> > >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::const_iterator = std::_Rb_tree<std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::_Identity<std::pair<long long int, long long int> >, std::less<std::pair<long long int, long long int> >, std::allocator<std::pair<long long int, long long int> > >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::node_type = std::_Rb_tree<std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::_Identity<std::pair<long long int, long long int> >, std::less<std::pair<long long int, long long int> >, std::allocator<std::pair<long long int, long long int> > >::node_type]' 588 | insert(const_iterator __hint, node_type&& __nh) | ^~~~~~ /usr/include/c++/10/bits/stl_multiset.h:588:7: note: candidate expects 2 arguments, 1 provided