| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 570820 | 1ne | Commuter Pass (JOI18_commuter_pass) | C++14 | Compilation error | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
struct point{
int64_t d,u,pp,bb;
};
struct cm {
bool operator()(const point& a, const point& b) const {
return a.d < b.d;
}
};
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int64_t n,m;cin>>n>>m;
int64_t S,T;cin>>S>>T;
--S;--T;
int64_t U,V;cin>>U>>V;
--U;--V;
vector<vector<pair<int64_t,int64_t>>>adj(n);
for (int64_t i = 0;i<m;++i){
int64_t x,y,z;cin>>x>>y>>z;
--x;--y;
adj[x].push_back({y,z});
adj[y].push_back({x,z});
}
const int64_t mxn = 1e18;
priority_queue<pair<int64_t,pair<int64_t,int64_t>>>q;
vector<vector<int64_t>>dist(n,vector<int64_t>(2,mxn));
q.push({0,{U,0}});
q.push({0,{V,1}});
dist[U][0] = 0;
dist[V][1] = 0;
while(!q.empty()){
auto u = q.top().second;
q.pop();
for (auto x:adj[u.first]){
if (dist[x.first][u.second] > dist[u.first][u.second] + x.second){
dist[x.first][u.second] = dist[u.first][u.second] + x.second;
q.push({-dist[x.first][u.second],{x.first,u.second}});
}
}
}
int64_t ans = dist[U][1];
vector<int64_t>dis(n,mxn);
map<int64_t,pair<int64_t,int64_t>>mp;
auto bfs = [&](){
multiset<point,cm>qq;
qq.insert({0LL,S,dist[S][0],dist[S][1]});
dis[S] = 0LL;
while(!qq.empty()){
auto u = *qq.begin();
qq.erase(qq.begin());
mp.erase(u.u);
if (u.d > dis[u.u])continue;
if (u.u == T){
ans = min(ans,u.pp + u.bb);
}
for (auto x:adj[u.u]){
if (dis[x.first] > dis[u.u] + x.second){
dis[x.first] = dis[u.u] + x.second;
qq.insert({dis[x.first],x.first,min(u.pp,dist[x.first][0]),min(u.bb,dist[x.first][1])});
mp[x.first] = make_pair(min(u.pp,dist[x.first][0]),min(u.bb,dist[x.first][1]));
}
else if (dis[x.first] == dis[u.u] + x.second && !mp.empty()){
if (mp[x.first].first > min(u.pp,dist[x.first][0]) || mp[x.second] > min(u.bb,dist[x.first][1])){
qq.insert({dis[x.first],x.first, min(u.pp,dist[x.first][0]),min(u.bb,dist[x.first][1])});
mp[x.first] = make_pair(min(u.pp,dist[x.first][0]),min(u.bb,dist[x.first][1]));
}
}
}
}
};
bfs();
cout<<ans<<'\n';
return 0;
}
Compilation message (stderr)
commuter_pass.cpp: In lambda function:
commuter_pass.cpp:65:73: error: no match for 'operator>' (operand types are 'std::map<long int, std::pair<long int, long int> >::mapped_type' {aka 'std::pair<long int, long int>'} and 'const long int')
65 | if (mp[x.first].first > min(u.pp,dist[x.first][0]) || mp[x.second] > min(u.bb,dist[x.first][1])){
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from commuter_pass.cpp:1:
/usr/include/c++/10/bits/regex.h:1108:5: note: candidate: 'template<class _BiIter> bool std::__cxx11::operator>(const std::__cxx11::sub_match<_BiIter>&, const std::__cxx11::sub_match<_BiIter>&)'
1108 | operator>(const sub_match<_BiIter>& __lhs, const sub_match<_BiIter>& __rhs)
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1108:5: note: template argument deduction/substitution failed:
commuter_pass.cpp:65:100: note: 'std::map<long int, std::pair<long int, long int> >::mapped_type' {aka 'std::pair<long int, long int>'} is not derived from 'const std::__cxx11::sub_match<_BiIter>'
65 | if (mp[x.first].first > min(u.pp,dist[x.first][0]) || mp[x.second] > min(u.bb,dist[x.first][1])){
| ^
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from commuter_pass.cpp:1:
/usr/include/c++/10/bits/regex.h:1168:5: note: candidate: 'template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator>(std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&, const std::__cxx11::sub_match<_BiIter>&)'
1168 | operator>(const __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1168:5: note: template argument deduction/substitution failed:
commuter_pass.cpp:65:100: note: 'std::map<long int, std::pair<long int, long int> >::mapped_type' {aka 'std::pair<long int, long int>'} is not derived from 'std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>'
65 | if (mp[x.first].first > min(u.pp,dist[x.first][0]) || mp[x.second] > min(u.bb,dist[x.first][1])){
| ^
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from commuter_pass.cpp:1:
/usr/include/c++/10/bits/regex.h:1261:5: note: candidate: 'template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator>(const std::__cxx11::sub_match<_BiIter>&, std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&)'
1261 | operator>(const sub_match<_Bi_iter>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1261:5: note: template argument deduction/substitution failed:
commuter_pass.cpp:65:100: note: 'std::map<long int, std::pair<long int, long int> >::mapped_type' {aka 'std::pair<long int, long int>'} is not derived from 'const std::__cxx11::sub_match<_BiIter>'
65 | if (mp[x.first].first > min(u.pp,dist[x.first][0]) || mp[x.second] > min(u.bb,dist[x.first][1])){
| ^
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from commuter_pass.cpp:1:
/usr/include/c++/10/bits/regex.h:1335:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator>(const typename std::iterator_traits<_Iter>::value_type*, const std::__cxx11::sub_match<_BiIter>&)'
1335 | operator>(typename iterator_traits<_Bi_iter>::value_type const* __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1335:5: note: template argument deduction/substitution failed:
commuter_pass.cpp:65:100: note: mismatched types 'const std::__cxx11::sub_match<_BiIter>' and 'const long int'
65 | if (mp[x.first].first > min(u.pp,dist[x.first][0]) || mp[x.second] > min(u.bb,dist[x.first][1])){
| ^
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from commuter_pass.cpp:1:
/usr/include/c++/10/bits/regex.h:1429:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator>(const std::__cxx11::sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type*)'
1429 | operator>(const sub_match<_Bi_iter>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1429:5: note: template argument deduction/substitution failed:
commuter_pass.cpp:65:100: note: 'std::map<long int, std::pair<long int, long int> >::mapped_type' {aka 'std::pair<long int, long int>'} is not derived from 'const std::__cxx11::sub_match<_BiIter>'
65 | if (mp[x.first].first > min(u.pp,dist[x.first][0]) || mp[x.second] > min(u.bb,dist[x.first][1])){
| ^
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from commuter_pass.cpp:1:
/usr/include/c++/10/bits/regex.h:1505:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator>(const typename std::iterator_traits<_Iter>::value_type&, const std::__cxx11::sub_match<_BiIter>&)'
1505 | operator>(typename iterator_traits<_Bi_iter>::value_type const& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1505:5: note: template argument deduction/substitution failed:
commuter_pass.cpp:65:100: note: mismatched types 'const std::__cxx11::sub_match<_BiIter>' and 'const long int'
65 | if (mp[x.first].first > min(u.pp,dist[x.first][0]) || mp[x.second] > min(u.bb,dist[x.first][1])){
| ^
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from commuter_pass.cpp:1:
/usr/include/c++/10/bits/regex.h:1605:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator>(const std::__cxx11::sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type&)'
1605 | operator>(const sub_match<_Bi_iter>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1605:5: note: template argument deduction/substitution failed:
commuter_pass.cpp:65:100: note: 'std::map<long int, std::pair<long int, long int> >::mapped_type' {aka 'std::pair<long int, long int>'} is not derived from 'const std::__cxx11::sub_match<_BiIter>'
65 | if (mp[x.first].first > min(u.pp,dist[x.first][0]) || mp[x.second] > min(u.bb,dist[x.first][1])){
| ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
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:1:
/usr/include/c++/10/bits/stl_pair.h:502:5: note: candidate: 'template<class _T1, class _T2> constexpr bool std::operator>(const std::pair<_T1, _T2>&, const std::pair<_T1, _T2>&)'
502 | operator>(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
| ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:502:5: note: template argument deduction/substitution failed:
commuter_pass.cpp:65:100: note: mismatched types 'const std::pair<_T1, _T2>' and 'const long int'
65 | if (mp[x.first].first > min(u.pp,dist[x.first][0]) || mp[x.second] > min(u.bb,dist[x.first][1])){
| ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
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:1:
/usr/include/c++/10/bits/stl_iterator.h:378:5: note: candidate: 'template<class _Iterator> bool std::operator>(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_Iterator>&)'
378 | operator>(const reverse_iterator<_Iterator>& __x,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:378:5: note: template argument deduction/substitution failed:
commuter_pass.cpp:65:100: note: 'std::map<long int, std::pair<long int, long int> >::mapped_type' {aka 'std::pair<long int, long int>'} is not derived from 'const std::reverse_iterator<_Iterator>'
65 | if (mp[x.first].first > min(u.pp,dist[x.first][0]) || mp[x.second] > min(u.bb,dist[x.first][1])){
| ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
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:1:
/usr/include/c++/10/bits/stl_iterator.h:416:5: note: candidate: 'template<class _IteratorL, class _IteratorR> bool std::operator>(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_IteratorR>&)'
416 | operator>(const reverse_iterator<_IteratorL>& __x,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:416:5: note: template argument deduction/substitution failed:
commuter_pass.cpp:65:100: note: 'std::map<long int, std::pair<long int, long int> >::mapped_type' {aka 'std::pair<long int, long int>'} is not derived from 'const std::reverse_iterator<_Iterator>'
65 | if (mp[x.first].first > min(u.pp,dist[x.first][0]) || mp[x.second] > min(u.bb,dist[x.first][1])){
| ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
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:1:
/usr/include/c++/10/bits/stl_iterator.h:1469:5: note: candidate: 'template<class _IteratorL, class _IteratorR> bool std::operator>(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorR>&)'
1469 | operator>(const move_iterator<_IteratorL>& __x,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1469:5: note: template argument deduction/substitution failed:
commuter_pass.cpp:65:100: note: 'std::map<long int, std::pair<long int, long int> >::mapped_type' {aka 'std::pair<long int, long int>'} is not derived from 'const std::move_iterator<_IteratorL>'
65 | if (mp[x.first].first > min(u.pp,dist[x.first][0]) || mp[x.second] > min(u.bb,dist[x.first][1])){
| ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
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:1:
/usr/include/c++/10/bits/stl_iterator.h:1519:5: note: candidate: 'template<class _Iterator> bool std::operator>(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorL>&)'
1519 | operator>(const move_iterator<_Iterator>& __x,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1519:5: note: template argument deduction/substitution failed:
commuter_pass.cpp:65:100: note: 'std::map<long int, std::pair<long int, long int> >::mapped_type' {aka 'std::pair<long int, long int>'} is not derived from 'const std::move_iterator<_IteratorL>'
65 | if (mp[x.first].first > min(u.pp,dist[x.first][0]) || mp[x.second] > min(u.bb,dist[x.first][1])){
| ^
In file included from /usr/include/c++/10/string:55,
from /usr/include/c++/10/bits/locale_classes.h:40,
from /usr/include/c++/10/bits/ios_base.h:41,
from /usr/include/c++/10/ios:42,
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:1:
/usr/include/c++/10/bits/basic_string.h:6305:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> bool std::operator>(const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&, const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&)'
6305 | operator>(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6305:5: note: template argument deduction/substitution failed:
commuter_pass.cpp:65:100: note: 'std::map<long int, std::pair<long int, long int> >::mapped_type' {aka 'std::pair<long int, long int>'} is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>'
65 | if (mp[x.first].first > min(u.pp,dist[x.first][0]) || mp[x.second] > min(u.bb,dist[x.first][1])){
| ^
In file included from /usr/include/c++/10/string:55,
from /usr/include/c++/10/bits/locale_classes.h:40,
from /usr/include/c++/10/bits/ios_base.h:41,
from /usr/include/c++/10/ios:42,
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:1:
/usr/include/c++/10/bits/basic_string.h:6318:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> bool std::operator>(const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&, const _CharT*)'
6318 | operator>(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6318:5: note: template argument deduction/substitution failed:
commuter_pass.cpp:65:100: note: 'std::map<long int, std::pair<long int, long int> >::mapped_type' {aka 'std::pair<long int, long int>'} is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>'
65 | if (mp[x.first].first > min(u.pp,dist[x.first][0]) || mp[x.second] > min(u.bb,dist[x.first][1])){
| ^
In file included from /usr/include/c++/10/string:55,
from /usr/include/c++/10/bits/locale_classes.h:40,
from /usr/include/c++/10/bits/ios_base.h:41,
from /usr/include/c++/10/ios:42,
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:1:
/usr/include/c++/10/bits/basic_string.h:6330:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> bool std::operator>(const _CharT*, const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&)'
6330 | operator>(const _CharT* __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6330:5: note: template argument deduction/substitution failed:
commuter_pass.cpp:65:100: note: mismatched types 'const _CharT*' and 'std::pair<long int, long int>'
65 | if (mp[x.first].first > min(u.pp,dist[x.first][0]) || mp[x.second] > min(u.bb,dist[x.first][1])){
| ^
In file included from /usr/include/c++/10/deque:67,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:68,
from commuter_pass.cpp:1:
/usr/include/c++/10/bits/stl_deque.h:2292:5: note: candidate: 'template<class _Tp, class _Alloc> bool std::operator>(const std::deque<_Tp, _Alloc>&, const std::deque<_Tp, _Alloc>&)'
2292 | operator>(const deque<_Tp, _Alloc>& __x, const deque<_Tp, _Alloc>& __y)
| ^~~~~~~~
/usr/include/c++/10/bits/stl_deque.h:2292:5: note: template argument deduction/substitution failed:
commuter_pass.cpp:65:100: note: 'std::map<long int, std::pair<long int, long int> >::mapped_type' {aka 'std::pair<long int, long int>'} is not derived from 'const std::deque<_Tp, _Alloc>'
65 | if (mp[x.first].first > min(u.pp,dist[x.first][0]) || mp[x.second] > min(u.bb,dist[x.first][1])){
| ^
In file included from /usr/include/c++/10/tuple:39,
from /usr/include/c++/10/functional:54,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:71,
from commuter_pass.cpp:1:
/usr/include/c++/10/array:293:5: note: candidate: 'template<class _Tp, long unsigned int _Nm> bool std::operator>(const std::array<_Tp