#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
vector<pair<int, int> > G[100100];
int N,M,S,T,U,V;
vector<long long> dist(int s)
{
vector<long long> ret(N,1e18);
priority_queue<pair<long long, int> > Q;
Q.push({0,s}); ret[s] = 0;
while (!Q.empty()){
long long c = -Q.top().first; int x = Q.top().second; Q.pop();
if (ret[x] < c) continue;
for (auto &e : G[x]){
int y = e.first; long long nc = c + e.second;
if (ret[y] > nc){
Q.push({-nc,y}); ret[y] = nc;
}
}
}
return move(ret);
}
int main()
{
scanf ("%d %d %d %d %d %d",&N,&M,&S,&T,&U,&V);
S--; T--; U--; V--;
for (int i=0;i<M;i++){
int x,y,c; scanf ("%d %d %d",&x,&y,&c); x--; y--;
G[x].push_back({y,c});
G[y].push_back({x,c});
}
auto s = dist(S);
auto t = dist(T);
auto u = dist(U);
auto v = dist(V);
vector<pair<long long, int> > st;
for (int i=0;i<N;i++) if (s[T] == s[i] + t[i]){
st.push_back({t[i],i});
}
sort(st.begin(),st.end());
vector<long long> um(N,1e18), vm(N,1e18);
long long ans = u[V];
for (auto &p : st){
int x = p.second;
um[x] = u[x];
vm[x] = v[x];
for (auto &e : G[x]){
if (t[e.first] + e.second == t[x]){
um[x] = min(um[x], um[e.first]);
vm[x] = min(vm[x], vm[e.first]);
}
}
ans = min(ans,um[x]+v[x]);
ans = min(ans,vm[x]+u[x]);
}
printf ("%lld\n",ans);
return 0;
}
Compilation message
commuter_pass.cpp: In function 'std::vector<long long int> dist(int)':
commuter_pass.cpp:25:13: warning: moving a local object in a return statement prevents copy elision [-Wpessimizing-move]
25 | return move(ret);
| ~~~~^~~~~
commuter_pass.cpp:25:13: note: remove 'std::move' call
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
30 | scanf ("%d %d %d %d %d %d",&N,&M,&S,&T,&U,&V);
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:33:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
33 | int x,y,c; scanf ("%d %d %d",&x,&y,&c); x--; y--;
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
239 ms |
15528 KB |
Output is correct |
2 |
Correct |
251 ms |
14980 KB |
Output is correct |
3 |
Correct |
252 ms |
15412 KB |
Output is correct |
4 |
Correct |
232 ms |
15424 KB |
Output is correct |
5 |
Correct |
239 ms |
18012 KB |
Output is correct |
6 |
Correct |
244 ms |
19220 KB |
Output is correct |
7 |
Correct |
251 ms |
18152 KB |
Output is correct |
8 |
Correct |
237 ms |
18064 KB |
Output is correct |
9 |
Correct |
241 ms |
18128 KB |
Output is correct |
10 |
Correct |
240 ms |
18236 KB |
Output is correct |
11 |
Correct |
86 ms |
13232 KB |
Output is correct |
12 |
Correct |
249 ms |
18052 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
281 ms |
14760 KB |
Output is correct |
2 |
Correct |
253 ms |
14800 KB |
Output is correct |
3 |
Correct |
258 ms |
14700 KB |
Output is correct |
4 |
Correct |
266 ms |
15056 KB |
Output is correct |
5 |
Correct |
290 ms |
14620 KB |
Output is correct |
6 |
Correct |
244 ms |
14988 KB |
Output is correct |
7 |
Correct |
272 ms |
15476 KB |
Output is correct |
8 |
Correct |
253 ms |
14796 KB |
Output is correct |
9 |
Correct |
266 ms |
14680 KB |
Output is correct |
10 |
Correct |
256 ms |
14736 KB |
Output is correct |
11 |
Correct |
96 ms |
11820 KB |
Output is correct |
12 |
Correct |
243 ms |
15072 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
3540 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
2 ms |
2644 KB |
Output is correct |
4 |
Correct |
15 ms |
4796 KB |
Output is correct |
5 |
Correct |
8 ms |
3624 KB |
Output is correct |
6 |
Correct |
2 ms |
2644 KB |
Output is correct |
7 |
Correct |
2 ms |
2772 KB |
Output is correct |
8 |
Correct |
3 ms |
2772 KB |
Output is correct |
9 |
Correct |
2 ms |
2700 KB |
Output is correct |
10 |
Correct |
10 ms |
3668 KB |
Output is correct |
11 |
Correct |
2 ms |
2644 KB |
Output is correct |
12 |
Correct |
3 ms |
2640 KB |
Output is correct |
13 |
Correct |
2 ms |
2644 KB |
Output is correct |
14 |
Correct |
2 ms |
2644 KB |
Output is correct |
15 |
Correct |
2 ms |
2644 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
239 ms |
15528 KB |
Output is correct |
2 |
Correct |
251 ms |
14980 KB |
Output is correct |
3 |
Correct |
252 ms |
15412 KB |
Output is correct |
4 |
Correct |
232 ms |
15424 KB |
Output is correct |
5 |
Correct |
239 ms |
18012 KB |
Output is correct |
6 |
Correct |
244 ms |
19220 KB |
Output is correct |
7 |
Correct |
251 ms |
18152 KB |
Output is correct |
8 |
Correct |
237 ms |
18064 KB |
Output is correct |
9 |
Correct |
241 ms |
18128 KB |
Output is correct |
10 |
Correct |
240 ms |
18236 KB |
Output is correct |
11 |
Correct |
86 ms |
13232 KB |
Output is correct |
12 |
Correct |
249 ms |
18052 KB |
Output is correct |
13 |
Correct |
281 ms |
14760 KB |
Output is correct |
14 |
Correct |
253 ms |
14800 KB |
Output is correct |
15 |
Correct |
258 ms |
14700 KB |
Output is correct |
16 |
Correct |
266 ms |
15056 KB |
Output is correct |
17 |
Correct |
290 ms |
14620 KB |
Output is correct |
18 |
Correct |
244 ms |
14988 KB |
Output is correct |
19 |
Correct |
272 ms |
15476 KB |
Output is correct |
20 |
Correct |
253 ms |
14796 KB |
Output is correct |
21 |
Correct |
266 ms |
14680 KB |
Output is correct |
22 |
Correct |
256 ms |
14736 KB |
Output is correct |
23 |
Correct |
96 ms |
11820 KB |
Output is correct |
24 |
Correct |
243 ms |
15072 KB |
Output is correct |
25 |
Correct |
9 ms |
3540 KB |
Output is correct |
26 |
Correct |
2 ms |
2644 KB |
Output is correct |
27 |
Correct |
2 ms |
2644 KB |
Output is correct |
28 |
Correct |
15 ms |
4796 KB |
Output is correct |
29 |
Correct |
8 ms |
3624 KB |
Output is correct |
30 |
Correct |
2 ms |
2644 KB |
Output is correct |
31 |
Correct |
2 ms |
2772 KB |
Output is correct |
32 |
Correct |
3 ms |
2772 KB |
Output is correct |
33 |
Correct |
2 ms |
2700 KB |
Output is correct |
34 |
Correct |
10 ms |
3668 KB |
Output is correct |
35 |
Correct |
2 ms |
2644 KB |
Output is correct |
36 |
Correct |
3 ms |
2640 KB |
Output is correct |
37 |
Correct |
2 ms |
2644 KB |
Output is correct |
38 |
Correct |
2 ms |
2644 KB |
Output is correct |
39 |
Correct |
2 ms |
2644 KB |
Output is correct |
40 |
Correct |
253 ms |
19424 KB |
Output is correct |
41 |
Correct |
232 ms |
18064 KB |
Output is correct |
42 |
Correct |
238 ms |
18040 KB |
Output is correct |
43 |
Correct |
100 ms |
14148 KB |
Output is correct |
44 |
Correct |
94 ms |
14148 KB |
Output is correct |
45 |
Correct |
270 ms |
18552 KB |
Output is correct |
46 |
Correct |
213 ms |
18340 KB |
Output is correct |
47 |
Correct |
239 ms |
18964 KB |
Output is correct |
48 |
Correct |
95 ms |
13560 KB |
Output is correct |
49 |
Correct |
200 ms |
19028 KB |
Output is correct |
50 |
Correct |
228 ms |
18556 KB |
Output is correct |
51 |
Correct |
212 ms |
18544 KB |
Output is correct |