#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
const int MOD = 1e9+7;
#define F first
#define S second
#define PB push_back
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
void FASTIO() {ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); }
const int MXN = 1e5+5;
const ll INF = 1e15;
int n, m;
int s, t, u, v;
vector<pii> adj[MXN];
vector<pii> dag[MXN]; // s -> t
ll dist_s[MXN], dist_t[MXN];
ll dist_u[MXN], dist_v[MXN];
void dijkstra(int start, ll dist[]) {
priority_queue<pli, vector<pli>, greater<pli>> PQ;
fill(dist, dist+n+1, INF);
dist[start] = 0;
PQ.push({0, start});
while(!PQ.empty()) {
ll d = PQ.top().F;
int i = PQ.top().S;
PQ.pop();
if(d != dist[i]) continue;
for(auto e : adj[i]) {
if(dist[e.F] > d+e.S) {
dist[e.F] = d+e.S;
PQ.push({dist[e.F], e.F});
}
}
}
}
bool visited[MXN];
pll mn[MXN]; // first - min dist to v, second - min dist to u
ll ans = INF;
void recur(int i) {
if(visited[i]) return;
visited[i] = true;
mn[i].F = dist_v[i];
mn[i].S = dist_u[i];
for(auto e : dag[i]) {
recur(e.F);
mn[i].F = min(mn[i].F, mn[e.F].F);
mn[i].S = min(mn[i].S, mn[e.F].S);
}
ans = min(ans, dist_u[i]+mn[i].F);
ans = min(ans, dist_v[i]+mn[i].S);
}
int main() {
FASTIO();
cin >> n >> m;
cin >> s >> t;
cin >> u >> v;
for(int i = 0; i < m; i++) {
int a, b, c; cin >> a >> b >> c;
adj[a].PB({b, c});
adj[b].PB({a, c});
}
dijkstra(s, dist_s);
dijkstra(t, dist_t);
dijkstra(u, dist_u);
dijkstra(v, dist_v);
for(int i = 1; i <= n; i++) {
for(auto e : adj[i]) {
if(dist_s[i]+dist_t[e.F]+e.S == dist_s[t]) {
dag[i].PB(e);
}
}
}
ans = dist_u[v];
for(int i = 1; i <= n; i++) {
if(!dag[i].empty()) {
recur(i);
}
}
cout << ans << "\n";
return 0;
}
/*
6 6
1 5
4 6
1 2 1
2 3 1
3 5 1
2 4 2
4 5 3
5 6 1
ans: 3
7 9
1 5
4 6
7 2 1
7 3 1
7 5 1
1 2 1
2 3 1
3 5 1
2 4 2
4 5 3
5 6 1
ans: 3
5 5
1 3
4 5
1 2 1
2 3 1
1 3 2
1 4 3
2 5 3
ans: 6
5 6
1 3
4 5
1 2 1
2 3 1
1 3 2
1 4 3
2 5 3
3 5 1
ans: 4
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
266 ms |
21276 KB |
Output is correct |
2 |
Correct |
246 ms |
19932 KB |
Output is correct |
3 |
Correct |
268 ms |
23424 KB |
Output is correct |
4 |
Correct |
243 ms |
21212 KB |
Output is correct |
5 |
Correct |
242 ms |
20716 KB |
Output is correct |
6 |
Correct |
269 ms |
21448 KB |
Output is correct |
7 |
Correct |
253 ms |
21004 KB |
Output is correct |
8 |
Correct |
281 ms |
20808 KB |
Output is correct |
9 |
Correct |
259 ms |
20504 KB |
Output is correct |
10 |
Correct |
220 ms |
20480 KB |
Output is correct |
11 |
Correct |
104 ms |
18512 KB |
Output is correct |
12 |
Correct |
256 ms |
20428 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
282 ms |
21008 KB |
Output is correct |
2 |
Correct |
305 ms |
21464 KB |
Output is correct |
3 |
Correct |
278 ms |
21324 KB |
Output is correct |
4 |
Correct |
291 ms |
20632 KB |
Output is correct |
5 |
Correct |
298 ms |
20912 KB |
Output is correct |
6 |
Correct |
280 ms |
23248 KB |
Output is correct |
7 |
Correct |
295 ms |
24196 KB |
Output is correct |
8 |
Correct |
303 ms |
20840 KB |
Output is correct |
9 |
Correct |
270 ms |
21320 KB |
Output is correct |
10 |
Correct |
277 ms |
21440 KB |
Output is correct |
11 |
Correct |
119 ms |
19828 KB |
Output is correct |
12 |
Correct |
257 ms |
23924 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
6188 KB |
Output is correct |
2 |
Correct |
3 ms |
5036 KB |
Output is correct |
3 |
Correct |
3 ms |
5076 KB |
Output is correct |
4 |
Correct |
14 ms |
7196 KB |
Output is correct |
5 |
Correct |
9 ms |
6060 KB |
Output is correct |
6 |
Correct |
4 ms |
5040 KB |
Output is correct |
7 |
Correct |
4 ms |
5164 KB |
Output is correct |
8 |
Correct |
5 ms |
5228 KB |
Output is correct |
9 |
Correct |
3 ms |
5076 KB |
Output is correct |
10 |
Correct |
9 ms |
6084 KB |
Output is correct |
11 |
Correct |
3 ms |
5032 KB |
Output is correct |
12 |
Correct |
3 ms |
4996 KB |
Output is correct |
13 |
Correct |
4 ms |
5032 KB |
Output is correct |
14 |
Correct |
4 ms |
5076 KB |
Output is correct |
15 |
Correct |
3 ms |
5076 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
266 ms |
21276 KB |
Output is correct |
2 |
Correct |
246 ms |
19932 KB |
Output is correct |
3 |
Correct |
268 ms |
23424 KB |
Output is correct |
4 |
Correct |
243 ms |
21212 KB |
Output is correct |
5 |
Correct |
242 ms |
20716 KB |
Output is correct |
6 |
Correct |
269 ms |
21448 KB |
Output is correct |
7 |
Correct |
253 ms |
21004 KB |
Output is correct |
8 |
Correct |
281 ms |
20808 KB |
Output is correct |
9 |
Correct |
259 ms |
20504 KB |
Output is correct |
10 |
Correct |
220 ms |
20480 KB |
Output is correct |
11 |
Correct |
104 ms |
18512 KB |
Output is correct |
12 |
Correct |
256 ms |
20428 KB |
Output is correct |
13 |
Correct |
282 ms |
21008 KB |
Output is correct |
14 |
Correct |
305 ms |
21464 KB |
Output is correct |
15 |
Correct |
278 ms |
21324 KB |
Output is correct |
16 |
Correct |
291 ms |
20632 KB |
Output is correct |
17 |
Correct |
298 ms |
20912 KB |
Output is correct |
18 |
Correct |
280 ms |
23248 KB |
Output is correct |
19 |
Correct |
295 ms |
24196 KB |
Output is correct |
20 |
Correct |
303 ms |
20840 KB |
Output is correct |
21 |
Correct |
270 ms |
21320 KB |
Output is correct |
22 |
Correct |
277 ms |
21440 KB |
Output is correct |
23 |
Correct |
119 ms |
19828 KB |
Output is correct |
24 |
Correct |
257 ms |
23924 KB |
Output is correct |
25 |
Correct |
9 ms |
6188 KB |
Output is correct |
26 |
Correct |
3 ms |
5036 KB |
Output is correct |
27 |
Correct |
3 ms |
5076 KB |
Output is correct |
28 |
Correct |
14 ms |
7196 KB |
Output is correct |
29 |
Correct |
9 ms |
6060 KB |
Output is correct |
30 |
Correct |
4 ms |
5040 KB |
Output is correct |
31 |
Correct |
4 ms |
5164 KB |
Output is correct |
32 |
Correct |
5 ms |
5228 KB |
Output is correct |
33 |
Correct |
3 ms |
5076 KB |
Output is correct |
34 |
Correct |
9 ms |
6084 KB |
Output is correct |
35 |
Correct |
3 ms |
5032 KB |
Output is correct |
36 |
Correct |
3 ms |
4996 KB |
Output is correct |
37 |
Correct |
4 ms |
5032 KB |
Output is correct |
38 |
Correct |
4 ms |
5076 KB |
Output is correct |
39 |
Correct |
3 ms |
5076 KB |
Output is correct |
40 |
Correct |
242 ms |
21788 KB |
Output is correct |
41 |
Correct |
246 ms |
20472 KB |
Output is correct |
42 |
Correct |
232 ms |
20536 KB |
Output is correct |
43 |
Correct |
111 ms |
20940 KB |
Output is correct |
44 |
Correct |
106 ms |
21024 KB |
Output is correct |
45 |
Correct |
235 ms |
22672 KB |
Output is correct |
46 |
Correct |
232 ms |
22548 KB |
Output is correct |
47 |
Correct |
230 ms |
21204 KB |
Output is correct |
48 |
Correct |
101 ms |
18572 KB |
Output is correct |
49 |
Correct |
193 ms |
21456 KB |
Output is correct |
50 |
Correct |
237 ms |
21992 KB |
Output is correct |
51 |
Correct |
221 ms |
22672 KB |
Output is correct |