#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define N 200005
#define INF 0x3f3f3f3f3f3f3f3f
int e[N], d[N], n, m, s, t, u, v;
vector<int> adj[N];
priority_queue<pair<ll, int> > p;
void dij(int v, ll* dis){
memset(dis, 0x3f3f, N << 3);
dis[v] = 0;
p.push({0, v});
while(!p.empty()){
v = p.top().ss;
if(p.top().ff != -dis[v]){
p.pop();
continue;
}
p.pop();
for(int& x : adj[v]){
int u = e[x] ^ v;
if(dis[u] > dis[v] + d[x]){
dis[u] = dis[v] + d[x];
p.push({-dis[u], u});
}
}
}
}
ll dis[3][N], dp[2][N], res;
void dfs(int v){
if(dp[0][v] != INF) return;
dp[1][v] = dis[1][v];
dp[0][v] = dis[0][v];
for(int& x : adj[v]){
int u = e[x] ^ v;
if(dis[2][u] == dis[2][v] - d[x]){
dfs(u);
dp[1][v] = min(dp[1][u], dp[1][v]);
dp[0][v] = min(dp[0][u], dp[0][v]);
}
}
res = min(res, min(dp[1][v] + dis[0][v], dp[0][v] + dis[1][v]));
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m>>s>>t>>u>>v;
for(int a, b, i = 1; i <= m; i++){
cin>>a>>b>>d[i];
e[i] = a ^ b;
adj[a].push_back(i);
adj[b].push_back(i);
}
memset(dp, 0x3f3f, sizeof dp);
dij(u, dis[0]);
dij(v, dis[1]);
dij(s, dis[2]);
res = dis[1][u];
dfs(t);
cout<<res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
317 ms |
19992 KB |
Output is correct |
2 |
Correct |
333 ms |
19944 KB |
Output is correct |
3 |
Correct |
330 ms |
23660 KB |
Output is correct |
4 |
Correct |
305 ms |
20032 KB |
Output is correct |
5 |
Correct |
301 ms |
19608 KB |
Output is correct |
6 |
Correct |
324 ms |
20052 KB |
Output is correct |
7 |
Correct |
320 ms |
19984 KB |
Output is correct |
8 |
Correct |
324 ms |
19956 KB |
Output is correct |
9 |
Correct |
317 ms |
19564 KB |
Output is correct |
10 |
Correct |
273 ms |
19564 KB |
Output is correct |
11 |
Correct |
152 ms |
19412 KB |
Output is correct |
12 |
Correct |
320 ms |
19624 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
320 ms |
21468 KB |
Output is correct |
2 |
Correct |
312 ms |
21660 KB |
Output is correct |
3 |
Correct |
338 ms |
21388 KB |
Output is correct |
4 |
Correct |
318 ms |
21480 KB |
Output is correct |
5 |
Correct |
345 ms |
21996 KB |
Output is correct |
6 |
Correct |
307 ms |
23248 KB |
Output is correct |
7 |
Correct |
349 ms |
23784 KB |
Output is correct |
8 |
Correct |
320 ms |
21608 KB |
Output is correct |
9 |
Correct |
337 ms |
21992 KB |
Output is correct |
10 |
Correct |
366 ms |
21416 KB |
Output is correct |
11 |
Correct |
148 ms |
20728 KB |
Output is correct |
12 |
Correct |
311 ms |
23432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
13404 KB |
Output is correct |
2 |
Correct |
13 ms |
12920 KB |
Output is correct |
3 |
Correct |
13 ms |
12920 KB |
Output is correct |
4 |
Correct |
31 ms |
13944 KB |
Output is correct |
5 |
Correct |
21 ms |
13304 KB |
Output is correct |
6 |
Correct |
14 ms |
12920 KB |
Output is correct |
7 |
Correct |
14 ms |
12920 KB |
Output is correct |
8 |
Correct |
14 ms |
12920 KB |
Output is correct |
9 |
Correct |
13 ms |
12920 KB |
Output is correct |
10 |
Correct |
21 ms |
13432 KB |
Output is correct |
11 |
Correct |
13 ms |
12920 KB |
Output is correct |
12 |
Correct |
13 ms |
12920 KB |
Output is correct |
13 |
Correct |
13 ms |
12920 KB |
Output is correct |
14 |
Correct |
13 ms |
12964 KB |
Output is correct |
15 |
Correct |
13 ms |
12920 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
317 ms |
19992 KB |
Output is correct |
2 |
Correct |
333 ms |
19944 KB |
Output is correct |
3 |
Correct |
330 ms |
23660 KB |
Output is correct |
4 |
Correct |
305 ms |
20032 KB |
Output is correct |
5 |
Correct |
301 ms |
19608 KB |
Output is correct |
6 |
Correct |
324 ms |
20052 KB |
Output is correct |
7 |
Correct |
320 ms |
19984 KB |
Output is correct |
8 |
Correct |
324 ms |
19956 KB |
Output is correct |
9 |
Correct |
317 ms |
19564 KB |
Output is correct |
10 |
Correct |
273 ms |
19564 KB |
Output is correct |
11 |
Correct |
152 ms |
19412 KB |
Output is correct |
12 |
Correct |
320 ms |
19624 KB |
Output is correct |
13 |
Correct |
320 ms |
21468 KB |
Output is correct |
14 |
Correct |
312 ms |
21660 KB |
Output is correct |
15 |
Correct |
338 ms |
21388 KB |
Output is correct |
16 |
Correct |
318 ms |
21480 KB |
Output is correct |
17 |
Correct |
345 ms |
21996 KB |
Output is correct |
18 |
Correct |
307 ms |
23248 KB |
Output is correct |
19 |
Correct |
349 ms |
23784 KB |
Output is correct |
20 |
Correct |
320 ms |
21608 KB |
Output is correct |
21 |
Correct |
337 ms |
21992 KB |
Output is correct |
22 |
Correct |
366 ms |
21416 KB |
Output is correct |
23 |
Correct |
148 ms |
20728 KB |
Output is correct |
24 |
Correct |
311 ms |
23432 KB |
Output is correct |
25 |
Correct |
22 ms |
13404 KB |
Output is correct |
26 |
Correct |
13 ms |
12920 KB |
Output is correct |
27 |
Correct |
13 ms |
12920 KB |
Output is correct |
28 |
Correct |
31 ms |
13944 KB |
Output is correct |
29 |
Correct |
21 ms |
13304 KB |
Output is correct |
30 |
Correct |
14 ms |
12920 KB |
Output is correct |
31 |
Correct |
14 ms |
12920 KB |
Output is correct |
32 |
Correct |
14 ms |
12920 KB |
Output is correct |
33 |
Correct |
13 ms |
12920 KB |
Output is correct |
34 |
Correct |
21 ms |
13432 KB |
Output is correct |
35 |
Correct |
13 ms |
12920 KB |
Output is correct |
36 |
Correct |
13 ms |
12920 KB |
Output is correct |
37 |
Correct |
13 ms |
12920 KB |
Output is correct |
38 |
Correct |
13 ms |
12964 KB |
Output is correct |
39 |
Correct |
13 ms |
12920 KB |
Output is correct |
40 |
Correct |
300 ms |
20064 KB |
Output is correct |
41 |
Correct |
301 ms |
19664 KB |
Output is correct |
42 |
Correct |
293 ms |
19592 KB |
Output is correct |
43 |
Correct |
162 ms |
19832 KB |
Output is correct |
44 |
Correct |
162 ms |
19848 KB |
Output is correct |
45 |
Correct |
294 ms |
19456 KB |
Output is correct |
46 |
Correct |
286 ms |
19300 KB |
Output is correct |
47 |
Correct |
286 ms |
19852 KB |
Output is correct |
48 |
Correct |
175 ms |
18008 KB |
Output is correct |
49 |
Correct |
267 ms |
19972 KB |
Output is correct |
50 |
Correct |
298 ms |
19420 KB |
Output is correct |
51 |
Correct |
286 ms |
19304 KB |
Output is correct |