#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 7;
int n;
int m;
int s;
int t;
int u;
int v;
int used[N];
long long res;
long long ds[N];
long long dt[N];
long long du[N];
long long dv[N];
long long dp[N];
vector<int> g1[N];
vector<pair<int, int>> g[N];
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> q;
void dij(int s, long long *d){
memset(d, 31, sizeof ds);
memset(used, 0, sizeof used);
d[s] = 0;
q.push({d[s], s});
while(!q.empty()){
int v = q.top().second;
q.pop();
if(used[v] == 1) continue;
used[v] = 1;
for(auto to: g[v]){
if(d[to.first] > d[v] + to.second){
d[to.first] = d[v] + to.second;
q.push({d[to.first], to.first});
}
}
}
}
void dfs(int x){
used[x] = 1;
dp[x] = dv[x];
for(auto to: g1[x]){
if(used[to] == 0) dfs(to);
dp[x] = min(dp[x], dp[to]);
}
res = min(res, du[x] + dp[x]);
}
int main()
{
ios_base::sync_with_stdio(false);
cin >> n >> m;
cin >> s >> t >> u >> v;
for(int i = 1; i <= m; i ++){
int x, y, w;
cin >> x >> y >> w;
g[x].push_back({y, w});
g[y].push_back({x, w});
}
dij(s, ds);
dij(t, dt);
dij(u, du);
dij(v, dv);
for(int x = 1; x <= n; x ++){
for(auto to: g[x]){
if(ds[x] + to.second + dt[to.first] == ds[t]){
g1[x].push_back(to.first);
}
}
}
res = du[v];
for(int i = 1; i <= 2; i ++){
memset(used, 0, sizeof used);
dfs(s);
swap(du, dv);
}
cout << res << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
383 ms |
28388 KB |
Output is correct |
2 |
Correct |
385 ms |
28780 KB |
Output is correct |
3 |
Correct |
425 ms |
33384 KB |
Output is correct |
4 |
Correct |
342 ms |
29060 KB |
Output is correct |
5 |
Correct |
384 ms |
29296 KB |
Output is correct |
6 |
Correct |
360 ms |
28232 KB |
Output is correct |
7 |
Correct |
436 ms |
29808 KB |
Output is correct |
8 |
Correct |
432 ms |
29556 KB |
Output is correct |
9 |
Correct |
372 ms |
28320 KB |
Output is correct |
10 |
Correct |
307 ms |
28268 KB |
Output is correct |
11 |
Correct |
181 ms |
25976 KB |
Output is correct |
12 |
Correct |
428 ms |
28364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
445 ms |
30312 KB |
Output is correct |
2 |
Correct |
442 ms |
30188 KB |
Output is correct |
3 |
Correct |
412 ms |
29804 KB |
Output is correct |
4 |
Correct |
390 ms |
30096 KB |
Output is correct |
5 |
Correct |
400 ms |
30560 KB |
Output is correct |
6 |
Correct |
440 ms |
32840 KB |
Output is correct |
7 |
Correct |
445 ms |
32880 KB |
Output is correct |
8 |
Correct |
431 ms |
30060 KB |
Output is correct |
9 |
Correct |
447 ms |
30600 KB |
Output is correct |
10 |
Correct |
410 ms |
29736 KB |
Output is correct |
11 |
Correct |
183 ms |
27768 KB |
Output is correct |
12 |
Correct |
382 ms |
33092 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
17784 KB |
Output is correct |
2 |
Correct |
13 ms |
16768 KB |
Output is correct |
3 |
Correct |
13 ms |
16768 KB |
Output is correct |
4 |
Correct |
35 ms |
18816 KB |
Output is correct |
5 |
Correct |
26 ms |
17792 KB |
Output is correct |
6 |
Correct |
13 ms |
17024 KB |
Output is correct |
7 |
Correct |
14 ms |
16896 KB |
Output is correct |
8 |
Correct |
19 ms |
17024 KB |
Output is correct |
9 |
Correct |
17 ms |
16896 KB |
Output is correct |
10 |
Correct |
20 ms |
17792 KB |
Output is correct |
11 |
Correct |
13 ms |
16768 KB |
Output is correct |
12 |
Correct |
13 ms |
16768 KB |
Output is correct |
13 |
Correct |
12 ms |
16768 KB |
Output is correct |
14 |
Correct |
12 ms |
16768 KB |
Output is correct |
15 |
Correct |
14 ms |
16896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
383 ms |
28388 KB |
Output is correct |
2 |
Correct |
385 ms |
28780 KB |
Output is correct |
3 |
Correct |
425 ms |
33384 KB |
Output is correct |
4 |
Correct |
342 ms |
29060 KB |
Output is correct |
5 |
Correct |
384 ms |
29296 KB |
Output is correct |
6 |
Correct |
360 ms |
28232 KB |
Output is correct |
7 |
Correct |
436 ms |
29808 KB |
Output is correct |
8 |
Correct |
432 ms |
29556 KB |
Output is correct |
9 |
Correct |
372 ms |
28320 KB |
Output is correct |
10 |
Correct |
307 ms |
28268 KB |
Output is correct |
11 |
Correct |
181 ms |
25976 KB |
Output is correct |
12 |
Correct |
428 ms |
28364 KB |
Output is correct |
13 |
Correct |
445 ms |
30312 KB |
Output is correct |
14 |
Correct |
442 ms |
30188 KB |
Output is correct |
15 |
Correct |
412 ms |
29804 KB |
Output is correct |
16 |
Correct |
390 ms |
30096 KB |
Output is correct |
17 |
Correct |
400 ms |
30560 KB |
Output is correct |
18 |
Correct |
440 ms |
32840 KB |
Output is correct |
19 |
Correct |
445 ms |
32880 KB |
Output is correct |
20 |
Correct |
431 ms |
30060 KB |
Output is correct |
21 |
Correct |
447 ms |
30600 KB |
Output is correct |
22 |
Correct |
410 ms |
29736 KB |
Output is correct |
23 |
Correct |
183 ms |
27768 KB |
Output is correct |
24 |
Correct |
382 ms |
33092 KB |
Output is correct |
25 |
Correct |
22 ms |
17784 KB |
Output is correct |
26 |
Correct |
13 ms |
16768 KB |
Output is correct |
27 |
Correct |
13 ms |
16768 KB |
Output is correct |
28 |
Correct |
35 ms |
18816 KB |
Output is correct |
29 |
Correct |
26 ms |
17792 KB |
Output is correct |
30 |
Correct |
13 ms |
17024 KB |
Output is correct |
31 |
Correct |
14 ms |
16896 KB |
Output is correct |
32 |
Correct |
19 ms |
17024 KB |
Output is correct |
33 |
Correct |
17 ms |
16896 KB |
Output is correct |
34 |
Correct |
20 ms |
17792 KB |
Output is correct |
35 |
Correct |
13 ms |
16768 KB |
Output is correct |
36 |
Correct |
13 ms |
16768 KB |
Output is correct |
37 |
Correct |
12 ms |
16768 KB |
Output is correct |
38 |
Correct |
12 ms |
16768 KB |
Output is correct |
39 |
Correct |
14 ms |
16896 KB |
Output is correct |
40 |
Correct |
363 ms |
28532 KB |
Output is correct |
41 |
Correct |
372 ms |
28308 KB |
Output is correct |
42 |
Correct |
392 ms |
28384 KB |
Output is correct |
43 |
Correct |
222 ms |
28280 KB |
Output is correct |
44 |
Correct |
194 ms |
28280 KB |
Output is correct |
45 |
Correct |
415 ms |
30576 KB |
Output is correct |
46 |
Correct |
414 ms |
30244 KB |
Output is correct |
47 |
Correct |
372 ms |
28552 KB |
Output is correct |
48 |
Correct |
228 ms |
26248 KB |
Output is correct |
49 |
Correct |
319 ms |
28312 KB |
Output is correct |
50 |
Correct |
372 ms |
29928 KB |
Output is correct |
51 |
Correct |
396 ms |
30576 KB |
Output is correct |