| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 670385 | kirakaminski968 | Commuter Pass (JOI18_commuter_pass) | C++17 | 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;
typedef long long ll;
ll N,M,S,T,U,V;
vector<pair<ll,ll>> graph(100001);
ll dp[2][100001],du[100001],dv[100001],ds[10001],ans;
bool vis[100001];
void dijkstra1(ll start, ll arr[]){
fill(vis, vis + 100001, false);
priority_queue<pair<ll, ll>> pq;
pq.push({0, start});
while (!pq.empty()) {
ll c, node;
tie(c, node) = pq.top();
pq.pop();
if (!vis[node]) {
arr[node] = -c;
vis[node] = true;
for (auto& i : graph[node]) pq.push({c - i.second, i.first});
}
}
}
void dijkstra2(ll start, ll ending){
fill(dp[0],dp[0]+100001,LLONG_MAX/2);
fill(dp[1],dp[1]+100001,LLONG_MAX/2);
fill(vis,vis+100001,false);
priority_queue<ll,pair<ll,ll>> pq; pq.push({0,{0,start});
dp[0][0] = dp[1][0] = LLONG_MAX/2;
while(!pq.empty()){
ll c, node, par;
pair<ll> p;
tie(c,p) = pq.top();
tie(node,par) = p;
if(!vis[node]){
vis[node] = true;
ds[node] = -c;
dp[0][node] = min(du[node],dp[0][par]); dp[1][node] = min(dv[node],dp[1][par]);
for(auto i : graph[node]) pq.push({c-i.second,{i.first,node}});
}
else if(-c == ds[node]){
if(min(du[node],dp[0][par]) + min(dv[node],dp[1][par]) <= dp[0][node] + dp[1][node]){
dp[0][node] = min(du[node],dp[0][par]);
dp[1][node] = min(dv[node],dp[1][par]);
}
}
}
ans = min(ans,dp[0][ending]+dp[1][ending]);
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N >> M >> S >> T >> U >> V;
for(int i = 0;i<M;i++){
ll a,b,c; cin >> a >> b >> c;
graph[a].push_back({b,c});
graph[b].push_back({a,c});
}
dijkstra1(u,du);
dijkstra1(v,dv);
ans = du[v];
dijkstra2(s,t);
dijkstra2(t,s);
cout << ans << endl;
return 0;
}
Compilation message (stderr)
commuter_pass.cpp: In function 'void dijkstra1(ll, ll*)':
commuter_pass.cpp:20:29: error: no matching function for call to 'begin(std::pair<long long int, long long int>&)'
20 | for (auto& i : graph[node]) pq.push({c - i.second, i.first});
| ^
In file included from /usr/include/c++/10/bits/range_access.h:36,
from /usr/include/c++/10/string:54,
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/initializer_list:90:5: note: candidate: 'template<class _Tp> constexpr const _Tp* std::begin(std::initializer_list<_Tp>)'
90 | begin(initializer_list<_Tp> __ils) noexcept
| ^~~~~
/usr/include/c++/10/initializer_list:90:5: note: template argument deduction/substitution failed:
commuter_pass.cpp:20:29: note: 'std::pair<long long int, long long int>' is not derived from 'std::initializer_list<_Tp>'
20 | for (auto& i : graph[node]) pq.push({c - i.second, i.first});
| ^
In file included from /usr/include/c++/10/string:54,
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/range_access.h:51:5: note: candidate: 'template<class _Container> constexpr decltype (__cont.begin()) std::begin(_Container&)'
51 | begin(_Container& __cont) -> decltype(__cont.begin())
| ^~~~~
/usr/include/c++/10/bits/range_access.h:51:5: note: template argument deduction/substitution failed:
/usr/include/c++/10/bits/range_access.h: In substitution of 'template<class _Container> constexpr decltype (__cont.begin()) std::begin(_Container&) [with _Container = std::pair<long long int, long long int>]':
commuter_pass.cpp:20:29: required from here
/usr/include/c++/10/bits/range_access.h:51:50: error: 'struct std::pair<long long int, long long int>' has no member named 'begin'
51 | begin(_Container& __cont) -> decltype(__cont.begin())
| ~~~~~~~^~~~~
/usr/include/c++/10/bits/range_access.h:61:5: note: candidate: 'template<class _Container> constexpr decltype (__cont.begin()) std::begin(const _Container&)'
61 | begin(const _Container& __cont) -> decltype(__cont.begin())
| ^~~~~
/usr/include/c++/10/bits/range_access.h:61:5: note: template argument deduction/substitution failed:
/usr/include/c++/10/bits/range_access.h: In substitution of 'template<class _Container> constexpr decltype (__cont.begin()) std::begin(const _Container&) [with _Container = std::pair<long long int, long long int>]':
commuter_pass.cpp:20:29: required from here
/usr/include/c++/10/bits/range_access.h:61:56: error: 'const struct std::pair<long long int, long long int>' has no member named 'begin'
61 | begin(const _Container& __cont) -> decltype(__cont.begin())
| ~~~~~~~^~~~~
/usr/include/c++/10/bits/range_access.h:90:5: note: candidate: 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::begin(_Tp (&)[_Nm])'
90 | begin(_Tp (&__arr)[_Nm])
| ^~~~~
/usr/include/c++/10/bits/range_access.h:90:5: note: template argument deduction/substitution failed:
commuter_pass.cpp:20:29: note: mismatched types '_Tp [_Nm]' and 'std::pair<long long int, long long int>'
20 | for (auto& i : graph[node]) pq.push({c - i.second, i.first});
| ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
from commuter_pass.cpp:1:
/usr/include/c++/10/valarray:1214:5: note: candidate: 'template<class _Tp> _Tp* std::begin(std::valarray<_Tp>&)'
1214 | begin(valarray<_Tp>& __va)
| ^~~~~
/usr/include/c++/10/valarray:1214:5: note: template argument deduction/substitution failed:
commuter_pass.cpp:20:29: note: 'std::pair<long long int, long long int>' is not derived from 'std::valarray<_Tp>'
20 | for (auto& i : graph[node]) pq.push({c - i.second, i.first});
| ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
from commuter_pass.cpp:1:
/usr/include/c++/10/valarray:1224:5: note: candidate: 'template<class _Tp> const _Tp* std::begin(const std::valarray<_Tp>&)'
1224 | begin(const valarray<_Tp>& __va)
| ^~~~~
/usr/include/c++/10/valarray:1224:5: note: template argument deduction/substitution failed:
commuter_pass.cpp:20:29: note: 'std::pair<long long int, long long int>' is not derived from 'const std::valarray<_Tp>'
20 | for (auto& i : graph[node]) pq.push({c - i.second, i.first});
| ^
commuter_pass.cpp:20:29: error: no matching function for call to 'end(std::pair<long long int, long long int>&)'
In file included from /usr/include/c++/10/bits/range_access.h:36,
from /usr/include/c++/10/string:54,
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/initializer_list:101:5: note: candidate: 'template<class _Tp> constexpr const _Tp* std::end(std::initializer_list<_Tp>)'
101 | end(initializer_list<_Tp> __ils) noexcept
| ^~~
/usr/include/c++/10/initializer_list:101:5: note: template argument deduction/substitution failed:
commuter_pass.cpp:20:29: note: 'std::pair<long long int, long long int>' is not derived from 'std::initializer_list<_Tp>'
20 | for (auto& i : graph[node]) pq.push({c - i.second, i.first});
| ^
In file included from /usr/include/c++/10/string:54,
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/range_access.h:71:5: note: candidate: 'template<class _Container> constexpr decltype (__cont.end()) std::end(_Container&)'
71 | end(_Container& __cont) -> decltype(__cont.end())
| ^~~
/usr/include/c++/10/bits/range_access.h:71:5: note: template argument deduction/substitution failed:
/usr/include/c++/10/bits/range_access.h: In substitution of 'template<class _Container> constexpr decltype (__cont.end()) std::end(_Container&) [with _Container = std::pair<long long int, long long int>]':
commuter_pass.cpp:20:29: required from here
/usr/include/c++/10/bits/range_access.h:71:48: error: 'struct std::pair<long long int, long long int>' has no member named 'end'
71 | end(_Container& __cont) -> decltype(__cont.end())
| ~~~~~~~^~~
/usr/include/c++/10/bits/range_access.h:81:5: note: candidate: 'template<class _Container> constexpr decltype (__cont.end()) std::end(const _Container&)'
81 | end(const _Container& __cont) -> decltype(__cont.end())
| ^~~
/usr/include/c++/10/bits/range_access.h:81:5: note: template argument deduction/substitution failed:
/usr/include/c++/10/bits/range_access.h: In substitution of 'template<class _Container> constexpr decltype (__cont.end()) std::end(const _Container&) [with _Container = std::pair<long long int, long long int>]':
commuter_pass.cpp:20:29: required from here
/usr/include/c++/10/bits/range_access.h:81:54: error: 'const struct std::pair<long long int, long long int>' has no member named 'end'
81 | end(const _Container& __cont) -> decltype(__cont.end())
| ~~~~~~~^~~
/usr/include/c++/10/bits/range_access.h:100:5: note: candidate: 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::end(_Tp (&)[_Nm])'
100 | end(_Tp (&__arr)[_Nm])
| ^~~
/usr/include/c++/10/bits/range_access.h:100:5: note: template argument deduction/substitution failed:
commuter_pass.cpp:20:29: note: mismatched types '_Tp [_Nm]' and 'std::pair<long long int, long long int>'
20 | for (auto& i : graph[node]) pq.push({c - i.second, i.first});
| ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
from commuter_pass.cpp:1:
/usr/include/c++/10/valarray:1234:5: note: candidate: 'template<class _Tp> _Tp* std::end(std::valarray<_Tp>&)'
1234 | end(valarray<_Tp>& __va)
| ^~~
/usr/include/c++/10/valarray:1234:5: note: template argument deduction/substitution failed:
commuter_pass.cpp:20:29: note: 'std::pair<long long int, long long int>' is not derived from 'std::valarray<_Tp>'
20 | for (auto& i : graph[node]) pq.push({c - i.second, i.first});
| ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
from commuter_pass.cpp:1:
/usr/include/c++/10/valarray:1244:5: note: candidate: 'template<class _Tp> const _Tp* std::end(const std::valarray<_Tp>&)'
1244 | end(const valarray<_Tp>& __va)
| ^~~
/usr/include/c++/10/valarray:1244:5: note: template argument deduction/substitution failed:
commuter_pass.cpp:20:29: note: 'std::pair<long long int, long long int>' is not derived from 'const std::valarray<_Tp>'
20 | for (auto& i : graph[node]) pq.push({c - i.second, i.first});
| ^
commuter_pass.cpp:20:63: error: no matching function for call to 'std::priority_queue<std::pair<long long int, long long int> >::push(<brace-enclosed initializer list>)'
20 | for (auto& i : graph[node]) pq.push({c - i.second, i.first});
| ^
In file included from /usr/include/c++/10/queue:64,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
from commuter_pass.cpp:1:
/usr/include/c++/10/bits/stl_queue.h:640:7: note: candidate: 'void std::priority_queue<_Tp, _Sequence, _Compare>::push(const value_type&) [with _Tp = std::pair<long long int, long long int>; _Sequence = std::vector<std::pair<long long int, long long int> >; _Compare = std::less<std::pair<long long int, long long int> >; std::priority_queue<_Tp, _Sequence, _Compare>::value_type = std::pair<long long int, long long int>]'
640 | push(const value_type& __x)
| ^~~~
/usr/include/c++/10/bits/stl_queue.h:640:30: 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>&'}
640 | push(const value_type& __x)
| ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_queue.h:648:7: note: candidate: 'void std::priority_queue<_Tp, _Sequence, _Compare>::push(std::priority_queue<_Tp, _Sequence, _Compare>::value_type&&) [with _Tp = std::pair<long long int, long long int>; _Sequence = std::vector<std::pair<long long int, long long int> >; _Compare = std::less<std::pair<long long int, long long int> >; std::priority_queue<_Tp, _Sequence, _Compare>::value_type = std::pair<long long int, long long int>]'
648 | push(value_type&& __x)
| ^~~~
/usr/include/c++/10/bits/stl_queue.h:648:25: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::priority_queue<std::pair<long long int, long long int> >::value_type&&' {aka 'std::pair<long long int, long long int>&&'}
648 | push(value_type&& __x)
| ~~~~~~~~~~~~~^~~
commuter_pass.cpp: In function 'void dijkstra2(ll, ll)':
commuter_pass.cpp:28:33: error: no type named 'value_type' in 'struct std::pair<long long int, long long int>'
28 | priority_queue<ll,pair<ll,ll>> pq; pq.push({0,{0,start});
| ^~
commuter_pass.cpp:28:33: error: template argument 3 is invalid
commuter_pass.cpp:28:43: error: request for member 'push' in 'pq', which is of non-class type 'int'
28 | priority_queue<ll,pair<ll,ll>> pq; pq.push({0,{0,start});
| ^~~~
commuter_pass.cpp:28:60: error: expected '}' before ')' token
28 | priority_queue<ll,pair<ll,ll>> pq; pq.push({0,{0,start});
| ~ ^
commuter_pass.cpp:30:15: error: request for member 'empty' in 'pq', which is of non-class type 'int'
30 | while(!pq.empty()){
| ^~~~~
commuter_pass.cpp:32:16: error: wrong number of template arguments (1, should be 2)
32 | pair<ll> p;
| ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
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 commuter_pass.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: provided for 'template<class _T1, class _T2> struct std::pair'
211 | struct pair
| ^~~~
commuter_pass.cpp:33:23: error: request for member 'top' in 'pq', which is of non-class type 'int'
33 | tie(c,p) = pq.top();
| ^~~
commuter_pass.cpp:34:25: error: no match for 'operator=' (operand types are 'std::tuple<long long int&, long long int&>' and 'int')
34 | tie(node,par) = p;
| ^
In file included from /usr/include/c++/10/functional:54,
from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
from /usr/include/c++/10/algorithm:74,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from commuter_pass.cpp:1:
/usr/include/c++/10/tuple:1173:7: note: candidate: 'std::tuple<_T1, _T2>& std::tuple<_T1, _T2>::operator=(typename std::conditional<__assignable<const _T1&, const _T2&>(), const std::tuple<_T1, _T2>&, const std::__nonesuch&>::type) [with _T1 = long long int&; _T2 = long long int&; typename std::conditional<__assignable<const _T1&, const _T2&>(), const std::tuple<_T1, _T2>&, const std::__nonesuch&>::type = const std::tuple<long long int&, long long int&>&]'
1173 | operator=(typename conditional<__assignable<const _T1&, const _T2&>(),
| ^~~~~~~~
/usr/include/c++/10/tuple:1175:35: note: no known conversion for argument 1 from 'int' to 'std::conditional<true, const std::tuple<long long int&, long long int&>&, const std::__nonesuch&>::type' {aka 'const std::tuple<long long int&, long long int&>&'}
1173 | operator=(typename conditional<__assignable<const _T1&, const _T2&>(),
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1174 | const tuple&,
| ~~~~~~~~~~~~~
1175 | const __nonesuch&>::type __in)
| ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
/usr/include/c++/10/tuple:1184:7: note: candidate: 'std::tuple<_T1, _T2>& std::tuple<_T1, _T2>::operator=(typename std::conditional<__assignable<_T1, _T2>(), std::tuple<_T1, _T2>&&, std::__nonesuch&&>::type) [with _T1 = long long int&; _T2 = long long int&; typename std::conditional<__assignable<_T1, _T2>(), std::tuple<_T1, _T2>&&, std::__nonesuch&&>::type = std::tuple<long long int&, long long int&>&&]'
1184 | operator=(typename conditional<__assignable<_T1, _T2>(),
| ^~~~~~~~
/usr/include/c++/10/tuple:1186:30: note: no known conversion for argument 1 from 'int' to 'std::conditional<true, std::tuple<long long int&, long long int&>&&, std::__nonesuch&&>::type' {aka 'std::tuple<long long int&, long long int&>&&'}
1184 | operator=(typename conditional<__assignable<_T1, _T2>(),
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1185 | tuple&&,
| ~~~~~~~~
1186 | __nonesuch&&>::type __in)
| ~~~~~~~~~~~~~~~~~~~~^~~~
/usr/include/c++/10/tuple:1196:2: note: candidate: 'template<class _U1, class _U2> std::__enable_if_t<__assignable<const _U1&, const _U2&>(), std::tuple<_T1, _T2>&> std::tuple<_T1, _T2>::operator=(const std::tuple<_U1, _U2>&) [with _U1 = _U1; _U2 = _U2; _T1 = long long int&; _T2 = long long int&]'
1196 | operator=(const tuple<_U1, _U2>& __in)
| ^~~~~~~~
/usr/include/c++/10/tuple:1196:2: note: template argument deduction/substitution failed:
commuter_pass.cpp:34:25: note: mismatched types 'const std::tuple<_T1, _T2>' and 'int'
34 | tie(node,par) = p;
| ^
In file included from /usr/include/c++/10/functional:54,
from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
from /usr/include/c++/10/algorithm:74,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from commuter_pass.cpp:1:
/usr/include/c++/10/tuple:1206:2: note: candidate: 'template<class _U1, class _U2> std::__enable_if_t<__assignable<_U1, _U2>(), std::tuple<_T1, _T2>&> std::tuple<_T1, _T2>::operator=(std::tuple<_U1, _U2>&&) [with _U1 = _U1; _U2 = _U2; _T1 = long long int&; _T2 = long long int&]'
1206 | operator=(tuple<_U1, _U2>&& __in)
| ^~~~~~~~
/usr/include/c++/10/tuple:1206:2: note: template argument deduction/substitution failed:
commuter_pass.cpp:34:25: note: mismatched types 'std::tuple<_T1, _T2>' and 'int'
34 | tie(node,par) = p;
| ^
In file included from /usr/include/c++/10/functional:54,
from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
from /usr/include/c++/10/algorithm:74,