/**
*
* *
* * *
* * * *
* *
* * *
* * * *
* * * * *
. * * * . *
* . O *
* O . * *
* * * * * *
* + * * * * *
* * o * * * * *
* * * * * * * * *
######
######
######
######
######
######
**/
#include <bits/stdc++.h>
using namespace std;
int n, m, S, T, U, V;
long long ds[100005], dt[100005], du[100005], dv[100005];
bool viz[100005], viz2[100005];
vector <pair <int, int> > v[100005];
priority_queue < pair <long long, int> , vector <pair <long long, int> > , greater <pair <long long, int> > > pq;
void dijkstra(int nod, long long d[]){
memset(viz, 0, sizeof(viz));
memset(viz2, 0, sizeof(viz2));
d[nod] = 0;
viz[nod] = 1;
pq.push({0, nod});
while(!pq.empty()){
int nod = pq.top().second;
pq.pop();
if(viz2[nod]) continue ;
viz2[nod] = 1;
for(auto it : v[nod]){
if(d[it.first] > d[nod] + it.second){
d[it.first] = d[nod] + it.second;
viz[it.first] = 1;
pq.push({d[it.first], it.first});
}
}
}
}
long long da[100005], db[100005], da2[100005], db2[100005];
long long Sol;
void solve(int S, int T, long long ds[], long long dt[], long long da[], long long db[]){
memset(viz, 0, sizeof(viz));
memset(viz2, 0, sizeof(viz2));
pq.push({0, S});
while(!pq.empty()){
int nod = pq.top().second;
pq.pop();
if(viz2[nod]) continue ;
viz2[nod] = 1;
for(auto it : v[nod]){
if(it.second + ds[nod] + dt[it.first] == ds[T]){
Sol = min(Sol, db[nod] + du[it.first]);
Sol = min(Sol, da[nod] + dv[it.first]);
da[it.first] = min(da[it.first], da[nod]);
db[it.first] = min(db[it.first], db[nod]);
viz[it.first] = 1;
pq.push({ds[it.first], it.first});
}
}
}
}
int main()
{
scanf("%d%d", &n, &m);
scanf("%d%d", &S, &T);
scanf("%d%d", &U, &V);
int x, y, c;
for(int i = 1; i <= m ; ++i){
scanf("%d%d%d", &x, &y, &c);
v[x].push_back({y, c});
v[y].push_back({x, c});
}
for(int i = 1; i <= n ; ++i) ds[i] = dt[i] = du[i] = dv[i] = 1e18;
dijkstra(S, ds);
dijkstra(T, dt);
dijkstra(U, du);
dijkstra(V, dv);
Sol = du[V];
// for(int i = 1; i <= n ; ++i)
// if(ds[i] + dt[i] == ds[T]) Sol = min(Sol, dv[i]);
for(int i = 1; i <= n ; ++i){
if(ds[i] + dt[i] == ds[T]){
da[i] = du[i];
db[i] = dv[i];
Sol = min(Sol, da[i] + db[i]);
}
else da[i] = db[i] = 1e18;
da2[i] = da[i];
db2[i] = db[i];
}
solve(S, T, ds, dt, da, db);
solve(T, S, dt, ds, da2, db2);
for(int i = 1; i <= n ; ++i){
if(ds[i] + dt[i] != ds[T]) continue ;
for(auto it : v[i]){
if(it.second + ds[i] + dt[it.first] == ds[T]){
Sol = min(Sol, da[i] + db2[it.first]);
Sol = min(Sol, db[i] + da2[it.first]);
}
}
}
printf("%lld", Sol);
return 0;
}
Compilation message
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:87:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~
commuter_pass.cpp:88:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &S, &T);
~~~~~^~~~~~~~~~~~~~~~
commuter_pass.cpp:89:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &U, &V);
~~~~~^~~~~~~~~~~~~~~~
commuter_pass.cpp:93:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &x, &y, &c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
388 ms |
17380 KB |
Output is correct |
2 |
Correct |
442 ms |
17080 KB |
Output is correct |
3 |
Correct |
469 ms |
20428 KB |
Output is correct |
4 |
Correct |
371 ms |
20452 KB |
Output is correct |
5 |
Correct |
435 ms |
19808 KB |
Output is correct |
6 |
Correct |
385 ms |
20572 KB |
Output is correct |
7 |
Correct |
456 ms |
19944 KB |
Output is correct |
8 |
Correct |
439 ms |
19960 KB |
Output is correct |
9 |
Correct |
377 ms |
20688 KB |
Output is correct |
10 |
Correct |
413 ms |
20588 KB |
Output is correct |
11 |
Correct |
263 ms |
14328 KB |
Output is correct |
12 |
Correct |
383 ms |
20588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
486 ms |
17228 KB |
Output is correct |
2 |
Correct |
417 ms |
19940 KB |
Output is correct |
3 |
Correct |
464 ms |
20072 KB |
Output is correct |
4 |
Correct |
449 ms |
20076 KB |
Output is correct |
5 |
Correct |
472 ms |
19956 KB |
Output is correct |
6 |
Correct |
544 ms |
20332 KB |
Output is correct |
7 |
Correct |
479 ms |
19972 KB |
Output is correct |
8 |
Correct |
454 ms |
19852 KB |
Output is correct |
9 |
Correct |
495 ms |
20052 KB |
Output is correct |
10 |
Correct |
465 ms |
19960 KB |
Output is correct |
11 |
Correct |
201 ms |
14392 KB |
Output is correct |
12 |
Correct |
467 ms |
20372 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
4216 KB |
Output is correct |
2 |
Correct |
5 ms |
2936 KB |
Output is correct |
3 |
Correct |
5 ms |
2936 KB |
Output is correct |
4 |
Correct |
23 ms |
4984 KB |
Output is correct |
5 |
Correct |
15 ms |
3960 KB |
Output is correct |
6 |
Correct |
6 ms |
3064 KB |
Output is correct |
7 |
Correct |
7 ms |
3064 KB |
Output is correct |
8 |
Correct |
17 ms |
3192 KB |
Output is correct |
9 |
Correct |
8 ms |
3064 KB |
Output is correct |
10 |
Correct |
14 ms |
3960 KB |
Output is correct |
11 |
Correct |
6 ms |
2936 KB |
Output is correct |
12 |
Correct |
5 ms |
2936 KB |
Output is correct |
13 |
Correct |
5 ms |
2936 KB |
Output is correct |
14 |
Correct |
5 ms |
2936 KB |
Output is correct |
15 |
Correct |
6 ms |
3064 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
388 ms |
17380 KB |
Output is correct |
2 |
Correct |
442 ms |
17080 KB |
Output is correct |
3 |
Correct |
469 ms |
20428 KB |
Output is correct |
4 |
Correct |
371 ms |
20452 KB |
Output is correct |
5 |
Correct |
435 ms |
19808 KB |
Output is correct |
6 |
Correct |
385 ms |
20572 KB |
Output is correct |
7 |
Correct |
456 ms |
19944 KB |
Output is correct |
8 |
Correct |
439 ms |
19960 KB |
Output is correct |
9 |
Correct |
377 ms |
20688 KB |
Output is correct |
10 |
Correct |
413 ms |
20588 KB |
Output is correct |
11 |
Correct |
263 ms |
14328 KB |
Output is correct |
12 |
Correct |
383 ms |
20588 KB |
Output is correct |
13 |
Correct |
486 ms |
17228 KB |
Output is correct |
14 |
Correct |
417 ms |
19940 KB |
Output is correct |
15 |
Correct |
464 ms |
20072 KB |
Output is correct |
16 |
Correct |
449 ms |
20076 KB |
Output is correct |
17 |
Correct |
472 ms |
19956 KB |
Output is correct |
18 |
Correct |
544 ms |
20332 KB |
Output is correct |
19 |
Correct |
479 ms |
19972 KB |
Output is correct |
20 |
Correct |
454 ms |
19852 KB |
Output is correct |
21 |
Correct |
495 ms |
20052 KB |
Output is correct |
22 |
Correct |
465 ms |
19960 KB |
Output is correct |
23 |
Correct |
201 ms |
14392 KB |
Output is correct |
24 |
Correct |
467 ms |
20372 KB |
Output is correct |
25 |
Correct |
20 ms |
4216 KB |
Output is correct |
26 |
Correct |
5 ms |
2936 KB |
Output is correct |
27 |
Correct |
5 ms |
2936 KB |
Output is correct |
28 |
Correct |
23 ms |
4984 KB |
Output is correct |
29 |
Correct |
15 ms |
3960 KB |
Output is correct |
30 |
Correct |
6 ms |
3064 KB |
Output is correct |
31 |
Correct |
7 ms |
3064 KB |
Output is correct |
32 |
Correct |
17 ms |
3192 KB |
Output is correct |
33 |
Correct |
8 ms |
3064 KB |
Output is correct |
34 |
Correct |
14 ms |
3960 KB |
Output is correct |
35 |
Correct |
6 ms |
2936 KB |
Output is correct |
36 |
Correct |
5 ms |
2936 KB |
Output is correct |
37 |
Correct |
5 ms |
2936 KB |
Output is correct |
38 |
Correct |
5 ms |
2936 KB |
Output is correct |
39 |
Correct |
6 ms |
3064 KB |
Output is correct |
40 |
Correct |
344 ms |
20820 KB |
Output is correct |
41 |
Correct |
438 ms |
20716 KB |
Output is correct |
42 |
Correct |
376 ms |
20712 KB |
Output is correct |
43 |
Correct |
168 ms |
14456 KB |
Output is correct |
44 |
Correct |
225 ms |
14460 KB |
Output is correct |
45 |
Correct |
554 ms |
19880 KB |
Output is correct |
46 |
Correct |
554 ms |
19536 KB |
Output is correct |
47 |
Correct |
367 ms |
20324 KB |
Output is correct |
48 |
Correct |
260 ms |
13944 KB |
Output is correct |
49 |
Correct |
311 ms |
20452 KB |
Output is correct |
50 |
Correct |
464 ms |
19564 KB |
Output is correct |
51 |
Correct |
487 ms |
19812 KB |
Output is correct |