#include <bits/stdc++.h>
// include <ext/pb_ds/assoc_container.hpp>
// include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
using namespace std;
#define all(x) x.begin(), x.end()
#define pb push_back
// define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
#define mpr make_pair
#define ln '\n'
void IO(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
#define int long long
bool chmin(int &x, int y){
bool flag = false;
if ( x > y ){
x = y; flag |= true;
}
return flag;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m; cin >> n >> m;
int s, t, u, v;
cin >> s >> t >> u >> v;
--s, --t, --u, --v;
vector <pair<int,int>> g[n];
for ( int i = 1; i <= m; i++ ){
int x, y, w; cin >> x >> y >> w;
g[--x].pb({--y, w});
g[y].pb({x, w});
}
const int inf = 1e17+1;
auto F = [&](int st){
vector <int> dis(n, inf);
dis[st] = 0;
priority_queue <pair<int,int>> q;
q.push({0, st});
while ( !q.empty() ){
auto [val, cur] = q.top();
q.pop(); val = -val;
if ( val != dis[cur] ) continue;
for ( auto [to, w]: g[cur] ){
if ( chmin(dis[to], val+w) ){
q.push({-dis[to], to});
}
}
}
return dis;
};
auto S = F(s), T = F(t), U = F(u), V = F(v);
vector <pair<int,int>> _list;
for ( int i = 0; i < n; i++ ){
if ( S[i]+T[i] == S[t] ){
_list.pb({T[i], i});
}
}
sort(all(_list), greater <pair<int,int>> ());
vector <int> dpU(n, inf), dpV(n, inf);
int Mn = U[v];
for ( auto [val, it]: _list ){
dpU[it] = U[it];
dpV[it] = V[it];
for ( auto [to, w]: g[it] ){
if ( T[it]+w == T[to] ){
chmin(dpU[it], dpU[to]);
chmin(dpV[it], dpV[to]);
}
}
chmin(Mn, dpU[it]+V[it]);
chmin(Mn, dpV[it]+U[it]);
}
cout << Mn;
cout << '\n';
}
Compilation message
commuter_pass.cpp: In function 'void IO(std::string)':
commuter_pass.cpp:11:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
11 | void IO(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:11:70: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
11 | void IO(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
264 ms |
23156 KB |
Output is correct |
2 |
Correct |
282 ms |
22208 KB |
Output is correct |
3 |
Correct |
292 ms |
22896 KB |
Output is correct |
4 |
Correct |
262 ms |
23040 KB |
Output is correct |
5 |
Correct |
277 ms |
22104 KB |
Output is correct |
6 |
Correct |
268 ms |
23184 KB |
Output is correct |
7 |
Correct |
293 ms |
22252 KB |
Output is correct |
8 |
Correct |
260 ms |
22244 KB |
Output is correct |
9 |
Correct |
258 ms |
22336 KB |
Output is correct |
10 |
Correct |
228 ms |
22312 KB |
Output is correct |
11 |
Correct |
105 ms |
15412 KB |
Output is correct |
12 |
Correct |
277 ms |
22304 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
270 ms |
22328 KB |
Output is correct |
2 |
Correct |
275 ms |
22212 KB |
Output is correct |
3 |
Correct |
278 ms |
22156 KB |
Output is correct |
4 |
Correct |
272 ms |
22228 KB |
Output is correct |
5 |
Correct |
275 ms |
22080 KB |
Output is correct |
6 |
Correct |
265 ms |
22740 KB |
Output is correct |
7 |
Correct |
279 ms |
22608 KB |
Output is correct |
8 |
Correct |
282 ms |
22224 KB |
Output is correct |
9 |
Correct |
284 ms |
22104 KB |
Output is correct |
10 |
Correct |
274 ms |
22052 KB |
Output is correct |
11 |
Correct |
111 ms |
15804 KB |
Output is correct |
12 |
Correct |
264 ms |
22676 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
2004 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
328 KB |
Output is correct |
4 |
Correct |
12 ms |
3788 KB |
Output is correct |
5 |
Correct |
7 ms |
1940 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
2 ms |
596 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
7 ms |
2004 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
264 ms |
23156 KB |
Output is correct |
2 |
Correct |
282 ms |
22208 KB |
Output is correct |
3 |
Correct |
292 ms |
22896 KB |
Output is correct |
4 |
Correct |
262 ms |
23040 KB |
Output is correct |
5 |
Correct |
277 ms |
22104 KB |
Output is correct |
6 |
Correct |
268 ms |
23184 KB |
Output is correct |
7 |
Correct |
293 ms |
22252 KB |
Output is correct |
8 |
Correct |
260 ms |
22244 KB |
Output is correct |
9 |
Correct |
258 ms |
22336 KB |
Output is correct |
10 |
Correct |
228 ms |
22312 KB |
Output is correct |
11 |
Correct |
105 ms |
15412 KB |
Output is correct |
12 |
Correct |
277 ms |
22304 KB |
Output is correct |
13 |
Correct |
270 ms |
22328 KB |
Output is correct |
14 |
Correct |
275 ms |
22212 KB |
Output is correct |
15 |
Correct |
278 ms |
22156 KB |
Output is correct |
16 |
Correct |
272 ms |
22228 KB |
Output is correct |
17 |
Correct |
275 ms |
22080 KB |
Output is correct |
18 |
Correct |
265 ms |
22740 KB |
Output is correct |
19 |
Correct |
279 ms |
22608 KB |
Output is correct |
20 |
Correct |
282 ms |
22224 KB |
Output is correct |
21 |
Correct |
284 ms |
22104 KB |
Output is correct |
22 |
Correct |
274 ms |
22052 KB |
Output is correct |
23 |
Correct |
111 ms |
15804 KB |
Output is correct |
24 |
Correct |
264 ms |
22676 KB |
Output is correct |
25 |
Correct |
7 ms |
2004 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
328 KB |
Output is correct |
28 |
Correct |
12 ms |
3788 KB |
Output is correct |
29 |
Correct |
7 ms |
1940 KB |
Output is correct |
30 |
Correct |
1 ms |
340 KB |
Output is correct |
31 |
Correct |
1 ms |
468 KB |
Output is correct |
32 |
Correct |
2 ms |
596 KB |
Output is correct |
33 |
Correct |
1 ms |
340 KB |
Output is correct |
34 |
Correct |
7 ms |
2004 KB |
Output is correct |
35 |
Correct |
1 ms |
340 KB |
Output is correct |
36 |
Correct |
1 ms |
340 KB |
Output is correct |
37 |
Correct |
1 ms |
340 KB |
Output is correct |
38 |
Correct |
1 ms |
340 KB |
Output is correct |
39 |
Correct |
1 ms |
332 KB |
Output is correct |
40 |
Correct |
243 ms |
22980 KB |
Output is correct |
41 |
Correct |
256 ms |
22204 KB |
Output is correct |
42 |
Correct |
280 ms |
22464 KB |
Output is correct |
43 |
Correct |
110 ms |
16188 KB |
Output is correct |
44 |
Correct |
105 ms |
16288 KB |
Output is correct |
45 |
Correct |
264 ms |
22632 KB |
Output is correct |
46 |
Correct |
247 ms |
22444 KB |
Output is correct |
47 |
Correct |
244 ms |
23008 KB |
Output is correct |
48 |
Correct |
109 ms |
15620 KB |
Output is correct |
49 |
Correct |
203 ms |
22680 KB |
Output is correct |
50 |
Correct |
231 ms |
22720 KB |
Output is correct |
51 |
Correct |
224 ms |
22724 KB |
Output is correct |