#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<pair<int, int>> adj[200100];
int dist[3][200100], dp[2][200100];
bitset<200100> vis;
void djikstra(int start, int ind) {
memset(dist[ind], 15, sizeof dist[ind]);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0,start});
dist[ind][start] = 0;
while(pq.size()) {
int x = pq.top().second, y = dist[ind][x];
pq.pop();
if(vis[x]) continue;
vis[x] = 1;
for(auto [to,weight]: adj[x])
if(y+weight < dist[ind][to])
pq.push({dist[ind][to]=y+weight,to});
}
vis.reset();
}
int ans;
void dfs(int n) {
vis[n] = 1;
dp[0][n] = dist[0][n];
dp[1][n] = dist[1][n];
for (auto [to, weight]: adj[n]) {
if (dist[2][n] - weight != dist[2][to]) continue;
if (!vis[to]) dfs(to);
dp[0][n] = min(dp[0][n], dp[0][to]);
dp[1][n] = min(dp[1][n], dp[1][to]);
}
ans = min(ans, min(dp[0][n] + dist[1][n], dp[1][n] + dist[0][n]));
}
signed main() {
cin.sync_with_stdio(false);
cin.tie(nullptr);
int n, m, s, t, u, v;
cin >> n >> m >> s >> t >> u >> v;
while(m--) {
int a, b, c;
cin >> a >> b >> c;
adj[a].push_back({b,c});
adj[b].push_back({a,c});
}
djikstra(u,0);
djikstra(v,1);
djikstra(s,2);
ans = dist[0][v];
dfs(t);
cout << ans << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
167 ms |
25500 KB |
Output is correct |
2 |
Correct |
178 ms |
24400 KB |
Output is correct |
3 |
Correct |
175 ms |
29184 KB |
Output is correct |
4 |
Correct |
150 ms |
24492 KB |
Output is correct |
5 |
Correct |
148 ms |
23064 KB |
Output is correct |
6 |
Correct |
165 ms |
24384 KB |
Output is correct |
7 |
Correct |
170 ms |
23172 KB |
Output is correct |
8 |
Correct |
171 ms |
23188 KB |
Output is correct |
9 |
Correct |
175 ms |
23168 KB |
Output is correct |
10 |
Correct |
127 ms |
22908 KB |
Output is correct |
11 |
Correct |
64 ms |
20936 KB |
Output is correct |
12 |
Correct |
168 ms |
22984 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
202 ms |
26268 KB |
Output is correct |
2 |
Correct |
182 ms |
26656 KB |
Output is correct |
3 |
Correct |
183 ms |
26120 KB |
Output is correct |
4 |
Correct |
185 ms |
26440 KB |
Output is correct |
5 |
Correct |
176 ms |
27004 KB |
Output is correct |
6 |
Correct |
178 ms |
28700 KB |
Output is correct |
7 |
Correct |
190 ms |
29252 KB |
Output is correct |
8 |
Correct |
201 ms |
26668 KB |
Output is correct |
9 |
Correct |
175 ms |
27084 KB |
Output is correct |
10 |
Correct |
176 ms |
26276 KB |
Output is correct |
11 |
Correct |
64 ms |
23456 KB |
Output is correct |
12 |
Correct |
172 ms |
29104 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
11476 KB |
Output is correct |
2 |
Correct |
4 ms |
9812 KB |
Output is correct |
3 |
Correct |
4 ms |
9812 KB |
Output is correct |
4 |
Correct |
14 ms |
13236 KB |
Output is correct |
5 |
Correct |
9 ms |
11476 KB |
Output is correct |
6 |
Correct |
4 ms |
9812 KB |
Output is correct |
7 |
Correct |
5 ms |
9940 KB |
Output is correct |
8 |
Correct |
5 ms |
9940 KB |
Output is correct |
9 |
Correct |
4 ms |
9784 KB |
Output is correct |
10 |
Correct |
9 ms |
11476 KB |
Output is correct |
11 |
Correct |
4 ms |
9740 KB |
Output is correct |
12 |
Correct |
4 ms |
9772 KB |
Output is correct |
13 |
Correct |
4 ms |
9684 KB |
Output is correct |
14 |
Correct |
4 ms |
9812 KB |
Output is correct |
15 |
Correct |
4 ms |
9812 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
167 ms |
25500 KB |
Output is correct |
2 |
Correct |
178 ms |
24400 KB |
Output is correct |
3 |
Correct |
175 ms |
29184 KB |
Output is correct |
4 |
Correct |
150 ms |
24492 KB |
Output is correct |
5 |
Correct |
148 ms |
23064 KB |
Output is correct |
6 |
Correct |
165 ms |
24384 KB |
Output is correct |
7 |
Correct |
170 ms |
23172 KB |
Output is correct |
8 |
Correct |
171 ms |
23188 KB |
Output is correct |
9 |
Correct |
175 ms |
23168 KB |
Output is correct |
10 |
Correct |
127 ms |
22908 KB |
Output is correct |
11 |
Correct |
64 ms |
20936 KB |
Output is correct |
12 |
Correct |
168 ms |
22984 KB |
Output is correct |
13 |
Correct |
202 ms |
26268 KB |
Output is correct |
14 |
Correct |
182 ms |
26656 KB |
Output is correct |
15 |
Correct |
183 ms |
26120 KB |
Output is correct |
16 |
Correct |
185 ms |
26440 KB |
Output is correct |
17 |
Correct |
176 ms |
27004 KB |
Output is correct |
18 |
Correct |
178 ms |
28700 KB |
Output is correct |
19 |
Correct |
190 ms |
29252 KB |
Output is correct |
20 |
Correct |
201 ms |
26668 KB |
Output is correct |
21 |
Correct |
175 ms |
27084 KB |
Output is correct |
22 |
Correct |
176 ms |
26276 KB |
Output is correct |
23 |
Correct |
64 ms |
23456 KB |
Output is correct |
24 |
Correct |
172 ms |
29104 KB |
Output is correct |
25 |
Correct |
9 ms |
11476 KB |
Output is correct |
26 |
Correct |
4 ms |
9812 KB |
Output is correct |
27 |
Correct |
4 ms |
9812 KB |
Output is correct |
28 |
Correct |
14 ms |
13236 KB |
Output is correct |
29 |
Correct |
9 ms |
11476 KB |
Output is correct |
30 |
Correct |
4 ms |
9812 KB |
Output is correct |
31 |
Correct |
5 ms |
9940 KB |
Output is correct |
32 |
Correct |
5 ms |
9940 KB |
Output is correct |
33 |
Correct |
4 ms |
9784 KB |
Output is correct |
34 |
Correct |
9 ms |
11476 KB |
Output is correct |
35 |
Correct |
4 ms |
9740 KB |
Output is correct |
36 |
Correct |
4 ms |
9772 KB |
Output is correct |
37 |
Correct |
4 ms |
9684 KB |
Output is correct |
38 |
Correct |
4 ms |
9812 KB |
Output is correct |
39 |
Correct |
4 ms |
9812 KB |
Output is correct |
40 |
Correct |
150 ms |
23872 KB |
Output is correct |
41 |
Correct |
157 ms |
23020 KB |
Output is correct |
42 |
Correct |
154 ms |
23184 KB |
Output is correct |
43 |
Correct |
65 ms |
21564 KB |
Output is correct |
44 |
Correct |
68 ms |
21628 KB |
Output is correct |
45 |
Correct |
155 ms |
22960 KB |
Output is correct |
46 |
Correct |
174 ms |
22952 KB |
Output is correct |
47 |
Correct |
150 ms |
23788 KB |
Output is correct |
48 |
Correct |
87 ms |
19152 KB |
Output is correct |
49 |
Correct |
134 ms |
23976 KB |
Output is correct |
50 |
Correct |
156 ms |
22960 KB |
Output is correct |
51 |
Correct |
174 ms |
23052 KB |
Output is correct |