#include <algorithm>
#include <set>
#include <vector>
#include <cstdio>
#define X first
#define Y second
#define PB push_back
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 10;
const ll OO = 1e18;
int n, m, s, t, a, b;
vector<pii> G[N];
ll DP[N], _DP[N], D[N];
auto comp = [](int a, int b) { return D[a] < D[b] || (D[a] == D[b] && a < b); };
set<int, decltype(comp)> S(comp);
void dijkstra(int s, vector<ll> &V) {
for(int i = 1; i <= n; ++i) D[i] = OO;
D[s] = 0;
S.insert(s);
for(; !S.empty(); ) {
int u = *S.begin();
S.erase(S.begin());
for(pii e : G[u])
if(D[e.X] > D[u] + e.Y) {
S.erase(e.X);
D[e.X] = D[u] + e.Y;
S.insert(e.X);
}
}
V.resize(N);
for(int i = 1; i <= n; ++i) V[i] = D[i];
}
vector<int> V;
vector<ll> DS, DT, DB, DA;
int main() {
scanf("%d%d%d%d%d%d", &n, &m, &s, &t, &a, &b);
for(int i = 0; i < m; ++i) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
G[u].PB({v, w});
G[v].PB({u, w});
}
dijkstra(s, DS);
dijkstra(t, DT);
dijkstra(b, DB);
for(int i = 1; i <= n; ++i) {
V.PB(i);
_DP[i] = OO;
DP[i] = OO;
}
sort(V.begin(), V.end(), [](int a, int b) { return DS[a] > DS[b]; });
for(int u : V) {
DP[u] = min(DP[u], DB[u]);
for(pii e : G[u])
if(DS[u] + e.Y + DT[e.X] == DS[t])
DP[u] = min(DP[u], DP[e.X]);
}
reverse(V.begin(), V.end());
for(int u : V) {
_DP[u] = min(_DP[u], DB[u]);
for(pii e : G[u])
if(DT[u] + e.Y + DS[e.X] == DT[s])
_DP[u] = min(_DP[u], _DP[e.X]);
}
ll ans = OO;
dijkstra(a, DA);
for(int u = 1; u <= n; ++u) ans = min(ans, DA[u] + min(_DP[u], DP[u]));
// for(int u = 1; u <= n; ++u) printf("%d : a %lld b %lld dp %lld\n", u, DA[u], DB[u], DP[u]);
printf("%lld\n", ans);
return 0;
}
Compilation message
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:51:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
51 | scanf("%d%d%d%d%d%d", &n, &m, &s, &t, &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
54 | scanf("%d%d%d", &u, &v, &w);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
357 ms |
17236 KB |
Output is correct |
2 |
Correct |
342 ms |
16308 KB |
Output is correct |
3 |
Correct |
309 ms |
16252 KB |
Output is correct |
4 |
Correct |
343 ms |
17272 KB |
Output is correct |
5 |
Correct |
313 ms |
16476 KB |
Output is correct |
6 |
Correct |
407 ms |
17396 KB |
Output is correct |
7 |
Correct |
386 ms |
16236 KB |
Output is correct |
8 |
Correct |
328 ms |
16508 KB |
Output is correct |
9 |
Correct |
354 ms |
16432 KB |
Output is correct |
10 |
Correct |
234 ms |
16460 KB |
Output is correct |
11 |
Correct |
77 ms |
11732 KB |
Output is correct |
12 |
Correct |
357 ms |
16276 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
380 ms |
16560 KB |
Output is correct |
2 |
Correct |
403 ms |
16200 KB |
Output is correct |
3 |
Correct |
366 ms |
16712 KB |
Output is correct |
4 |
Correct |
372 ms |
16156 KB |
Output is correct |
5 |
Correct |
403 ms |
16280 KB |
Output is correct |
6 |
Correct |
318 ms |
16180 KB |
Output is correct |
7 |
Correct |
344 ms |
16212 KB |
Output is correct |
8 |
Correct |
397 ms |
16224 KB |
Output is correct |
9 |
Correct |
387 ms |
16348 KB |
Output is correct |
10 |
Correct |
403 ms |
16192 KB |
Output is correct |
11 |
Correct |
70 ms |
11656 KB |
Output is correct |
12 |
Correct |
354 ms |
16224 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
7772 KB |
Output is correct |
2 |
Correct |
4 ms |
7260 KB |
Output is correct |
3 |
Correct |
3 ms |
7260 KB |
Output is correct |
4 |
Correct |
12 ms |
8536 KB |
Output is correct |
5 |
Correct |
7 ms |
7772 KB |
Output is correct |
6 |
Correct |
3 ms |
7260 KB |
Output is correct |
7 |
Correct |
3 ms |
7256 KB |
Output is correct |
8 |
Correct |
4 ms |
7260 KB |
Output is correct |
9 |
Correct |
3 ms |
7260 KB |
Output is correct |
10 |
Correct |
8 ms |
7876 KB |
Output is correct |
11 |
Correct |
2 ms |
7260 KB |
Output is correct |
12 |
Correct |
3 ms |
7260 KB |
Output is correct |
13 |
Correct |
3 ms |
7512 KB |
Output is correct |
14 |
Correct |
3 ms |
7260 KB |
Output is correct |
15 |
Correct |
3 ms |
7260 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
357 ms |
17236 KB |
Output is correct |
2 |
Correct |
342 ms |
16308 KB |
Output is correct |
3 |
Correct |
309 ms |
16252 KB |
Output is correct |
4 |
Correct |
343 ms |
17272 KB |
Output is correct |
5 |
Correct |
313 ms |
16476 KB |
Output is correct |
6 |
Correct |
407 ms |
17396 KB |
Output is correct |
7 |
Correct |
386 ms |
16236 KB |
Output is correct |
8 |
Correct |
328 ms |
16508 KB |
Output is correct |
9 |
Correct |
354 ms |
16432 KB |
Output is correct |
10 |
Correct |
234 ms |
16460 KB |
Output is correct |
11 |
Correct |
77 ms |
11732 KB |
Output is correct |
12 |
Correct |
357 ms |
16276 KB |
Output is correct |
13 |
Correct |
380 ms |
16560 KB |
Output is correct |
14 |
Correct |
403 ms |
16200 KB |
Output is correct |
15 |
Correct |
366 ms |
16712 KB |
Output is correct |
16 |
Correct |
372 ms |
16156 KB |
Output is correct |
17 |
Correct |
403 ms |
16280 KB |
Output is correct |
18 |
Correct |
318 ms |
16180 KB |
Output is correct |
19 |
Correct |
344 ms |
16212 KB |
Output is correct |
20 |
Correct |
397 ms |
16224 KB |
Output is correct |
21 |
Correct |
387 ms |
16348 KB |
Output is correct |
22 |
Correct |
403 ms |
16192 KB |
Output is correct |
23 |
Correct |
70 ms |
11656 KB |
Output is correct |
24 |
Correct |
354 ms |
16224 KB |
Output is correct |
25 |
Correct |
9 ms |
7772 KB |
Output is correct |
26 |
Correct |
4 ms |
7260 KB |
Output is correct |
27 |
Correct |
3 ms |
7260 KB |
Output is correct |
28 |
Correct |
12 ms |
8536 KB |
Output is correct |
29 |
Correct |
7 ms |
7772 KB |
Output is correct |
30 |
Correct |
3 ms |
7260 KB |
Output is correct |
31 |
Correct |
3 ms |
7256 KB |
Output is correct |
32 |
Correct |
4 ms |
7260 KB |
Output is correct |
33 |
Correct |
3 ms |
7260 KB |
Output is correct |
34 |
Correct |
8 ms |
7876 KB |
Output is correct |
35 |
Correct |
2 ms |
7260 KB |
Output is correct |
36 |
Correct |
3 ms |
7260 KB |
Output is correct |
37 |
Correct |
3 ms |
7512 KB |
Output is correct |
38 |
Correct |
3 ms |
7260 KB |
Output is correct |
39 |
Correct |
3 ms |
7260 KB |
Output is correct |
40 |
Correct |
437 ms |
18508 KB |
Output is correct |
41 |
Correct |
385 ms |
16576 KB |
Output is correct |
42 |
Correct |
369 ms |
16596 KB |
Output is correct |
43 |
Correct |
85 ms |
11660 KB |
Output is correct |
44 |
Correct |
75 ms |
11876 KB |
Output is correct |
45 |
Correct |
228 ms |
16144 KB |
Output is correct |
46 |
Correct |
237 ms |
16240 KB |
Output is correct |
47 |
Correct |
431 ms |
17224 KB |
Output is correct |
48 |
Correct |
85 ms |
11756 KB |
Output is correct |
49 |
Correct |
295 ms |
18372 KB |
Output is correct |
50 |
Correct |
287 ms |
16136 KB |
Output is correct |
51 |
Correct |
237 ms |
16188 KB |
Output is correct |