#include <bits/stdc++.h>
#define maxn 100010
using namespace std;
typedef long long ll;
typedef pair<ll, int> pl;
int n, m, s, t, u, v;
vector<pl> graph[maxn];
vector<ll> dist;
vector<ll> du(maxn, 1ll << 50), dv(maxn, 1ll << 50);
vector<int> prv[maxn], nxt[maxn];
priority_queue< pl, vector<pl>, greater<pl> > pq;
vector<int> ind(maxn);
bool in[maxn];
void dijkstra(int x, bool z1, bool z2){
dist.assign(maxn, 1ll << 50);
dist[x] = 0;
pq.push(make_pair(0, x));
while(! pq.empty()){
pl p = pq.top(); pq.pop();
int y = p.second; ll d = p.first;
if (d > dist[y]) continue;
for (int i = 0; i < graph[y].size(); i ++){
int to = graph[y][i].second;
ll w = graph[y][i].first;
if (w + d < dist[to]){
dist[to] = w + d;
pq.push(make_pair(dist[to], to));
if (z1){
prv[to].clear();
prv[to].push_back(y);
} else if (z2){
nxt[to].clear();
nxt[to].push_back(y);
}
} else if (w + d == dist[to]){
if (z1) prv[to].push_back(y);
else if (z2) nxt[to].push_back(y);
}
}
}
}
void bfs(vector<ll> &dp1, vector<ll> &dp2, int st){
queue<int> que;
que.push(st);
dp1[st] = dv[st];
dp2[st] = du[st];
while(! que.empty()){
int p = que.front(); que.pop();
in[p] = true;
int sz = (st == s ? nxt[p].size() : prv[p].size());
for (int i = 0; i < sz; i ++){
int to = (st == s ? nxt[p][i] : prv[p][i]);
dp1[to] = min(dp1[to], min(dp1[p], dv[to]));
dp2[to] = min(dp2[to], min(dp2[p], du[to]));
ind[to] --;
if (ind[to] == 0) que.push(to);
}
}
}
int main(){
cin >> n >> m >> s >> t >> u >> v;
s --; t --; u --; v --;
for (int i = 0; i < m; i ++){
int x, y; ll w;
cin >> x >> y >> w;
x --; y --;
graph[x].push_back(make_pair(w, y));
graph[y].push_back(make_pair(w, x));
}
dijkstra(s, true, false);
dijkstra(t, false, true);
dijkstra(u, false, false);
du = dist;
dijkstra(v, false, false);
dv = dist;
ll ans = dv[u];
vector<ll> dp_fv(maxn, 1ll << 50), dp_bv(maxn, 1ll << 50), dp_fu(maxn, 1ll << 50), dp_bu(maxn, 1ll << 50);
for (int i = 0; i < n; i ++){
ind[i] = prv[i].size();
}
bfs(dp_fv, dp_fu, s);
for (int i = 0; i < n; i ++){
ind[i] = nxt[i].size();
}
bfs(dp_bv, dp_bu, t);
for (int i = 0; i < n; i ++){
if (in[i]){
ans = min(ans, dp_fu[i] + dp_bv[i]);
ans = min(ans, dp_fv[i] + dp_bu[i]);
}
}
cout << ans << endl;
}
Compilation message
commuter_pass.cpp: In function 'void dijkstra(int, bool, bool)':
commuter_pass.cpp:23:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | for (int i = 0; i < graph[y].size(); i ++){
| ~~^~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
506 ms |
30260 KB |
Output is correct |
2 |
Correct |
640 ms |
30236 KB |
Output is correct |
3 |
Correct |
561 ms |
30260 KB |
Output is correct |
4 |
Correct |
508 ms |
30236 KB |
Output is correct |
5 |
Correct |
601 ms |
30196 KB |
Output is correct |
6 |
Correct |
595 ms |
30388 KB |
Output is correct |
7 |
Correct |
593 ms |
30172 KB |
Output is correct |
8 |
Correct |
542 ms |
33684 KB |
Output is correct |
9 |
Correct |
600 ms |
34212 KB |
Output is correct |
10 |
Correct |
496 ms |
34316 KB |
Output is correct |
11 |
Correct |
239 ms |
26508 KB |
Output is correct |
12 |
Correct |
541 ms |
34296 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
582 ms |
30280 KB |
Output is correct |
2 |
Correct |
573 ms |
33592 KB |
Output is correct |
3 |
Correct |
597 ms |
33592 KB |
Output is correct |
4 |
Correct |
576 ms |
33568 KB |
Output is correct |
5 |
Correct |
590 ms |
33600 KB |
Output is correct |
6 |
Correct |
569 ms |
34104 KB |
Output is correct |
7 |
Correct |
589 ms |
33524 KB |
Output is correct |
8 |
Correct |
681 ms |
33584 KB |
Output is correct |
9 |
Correct |
625 ms |
33552 KB |
Output is correct |
10 |
Correct |
549 ms |
33496 KB |
Output is correct |
11 |
Correct |
287 ms |
26548 KB |
Output is correct |
12 |
Correct |
559 ms |
34136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
14532 KB |
Output is correct |
2 |
Correct |
8 ms |
13260 KB |
Output is correct |
3 |
Correct |
8 ms |
13260 KB |
Output is correct |
4 |
Correct |
56 ms |
16732 KB |
Output is correct |
5 |
Correct |
29 ms |
14928 KB |
Output is correct |
6 |
Correct |
10 ms |
13260 KB |
Output is correct |
7 |
Correct |
11 ms |
13372 KB |
Output is correct |
8 |
Correct |
12 ms |
13516 KB |
Output is correct |
9 |
Correct |
9 ms |
13260 KB |
Output is correct |
10 |
Correct |
32 ms |
14924 KB |
Output is correct |
11 |
Correct |
8 ms |
13260 KB |
Output is correct |
12 |
Correct |
8 ms |
13292 KB |
Output is correct |
13 |
Correct |
8 ms |
13296 KB |
Output is correct |
14 |
Correct |
9 ms |
13260 KB |
Output is correct |
15 |
Correct |
9 ms |
13260 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
506 ms |
30260 KB |
Output is correct |
2 |
Correct |
640 ms |
30236 KB |
Output is correct |
3 |
Correct |
561 ms |
30260 KB |
Output is correct |
4 |
Correct |
508 ms |
30236 KB |
Output is correct |
5 |
Correct |
601 ms |
30196 KB |
Output is correct |
6 |
Correct |
595 ms |
30388 KB |
Output is correct |
7 |
Correct |
593 ms |
30172 KB |
Output is correct |
8 |
Correct |
542 ms |
33684 KB |
Output is correct |
9 |
Correct |
600 ms |
34212 KB |
Output is correct |
10 |
Correct |
496 ms |
34316 KB |
Output is correct |
11 |
Correct |
239 ms |
26508 KB |
Output is correct |
12 |
Correct |
541 ms |
34296 KB |
Output is correct |
13 |
Correct |
582 ms |
30280 KB |
Output is correct |
14 |
Correct |
573 ms |
33592 KB |
Output is correct |
15 |
Correct |
597 ms |
33592 KB |
Output is correct |
16 |
Correct |
576 ms |
33568 KB |
Output is correct |
17 |
Correct |
590 ms |
33600 KB |
Output is correct |
18 |
Correct |
569 ms |
34104 KB |
Output is correct |
19 |
Correct |
589 ms |
33524 KB |
Output is correct |
20 |
Correct |
681 ms |
33584 KB |
Output is correct |
21 |
Correct |
625 ms |
33552 KB |
Output is correct |
22 |
Correct |
549 ms |
33496 KB |
Output is correct |
23 |
Correct |
287 ms |
26548 KB |
Output is correct |
24 |
Correct |
559 ms |
34136 KB |
Output is correct |
25 |
Correct |
32 ms |
14532 KB |
Output is correct |
26 |
Correct |
8 ms |
13260 KB |
Output is correct |
27 |
Correct |
8 ms |
13260 KB |
Output is correct |
28 |
Correct |
56 ms |
16732 KB |
Output is correct |
29 |
Correct |
29 ms |
14928 KB |
Output is correct |
30 |
Correct |
10 ms |
13260 KB |
Output is correct |
31 |
Correct |
11 ms |
13372 KB |
Output is correct |
32 |
Correct |
12 ms |
13516 KB |
Output is correct |
33 |
Correct |
9 ms |
13260 KB |
Output is correct |
34 |
Correct |
32 ms |
14924 KB |
Output is correct |
35 |
Correct |
8 ms |
13260 KB |
Output is correct |
36 |
Correct |
8 ms |
13292 KB |
Output is correct |
37 |
Correct |
8 ms |
13296 KB |
Output is correct |
38 |
Correct |
9 ms |
13260 KB |
Output is correct |
39 |
Correct |
9 ms |
13260 KB |
Output is correct |
40 |
Correct |
604 ms |
34160 KB |
Output is correct |
41 |
Correct |
535 ms |
34224 KB |
Output is correct |
42 |
Correct |
554 ms |
34416 KB |
Output is correct |
43 |
Correct |
263 ms |
26540 KB |
Output is correct |
44 |
Correct |
260 ms |
26648 KB |
Output is correct |
45 |
Correct |
574 ms |
33264 KB |
Output is correct |
46 |
Correct |
539 ms |
33092 KB |
Output is correct |
47 |
Correct |
534 ms |
34036 KB |
Output is correct |
48 |
Correct |
247 ms |
26000 KB |
Output is correct |
49 |
Correct |
487 ms |
34188 KB |
Output is correct |
50 |
Correct |
580 ms |
33512 KB |
Output is correct |
51 |
Correct |
541 ms |
33292 KB |
Output is correct |