#include<bits/stdc++.h>
using namespace std;
long long n,m;
vector <pair <long long,long long> > g[100100];
vector <pair <long long,long long> > gg[100100];
long long dists[100100],distv[100100],distu[100100];
void dijkstra(long long dist[],long long s){
memset(dist,0x3f, sizeof (long long) * (n + 10));
dist[s] = 0;
priority_queue <pair <long long,long long> ,vector <pair <long long,long long> > ,greater <pair <long long,long long > > > q;
for (long long i = 1;i <= n; i++){
q.push({dist[i],i});
}
while (!q.empty()){
long long u = q.top().second;
long long val = q.top().first;
q.pop();
if (val != dist[u])continue;
for (auto tmp:g[u]){
long long v = tmp.first;
long long len = tmp.second;
if (dist[v] > dist[u] + len){
dist[v] = dist[u] + len;
q.push({dist[v],v});
}
}
}
}
bool in[100100];
long long dp[2][100100];
void dfs(long long u){
dp[0][u] = distu[u];
dp[1][u] = distv[u];
in[u] = 1;
for (auto v:g[u]){
if (dists[v.first] + v.second == dists[u]){
if (!in[v.first]){
dfs(v.first);
}
dp[0][u] = min(dp[0][u],dp[0][v.first]);
dp[1][u] = min(dp[1][u],dp[1][v.first]);
}
}
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
cin>>n>>m;
long long s,t,u,v;
cin>>s>>t>>u>>v;
for (long long i = 1;i <= m;i ++){
long long uu,vv,w;
cin>>uu>>vv>>w;
g[uu].push_back({vv,w});
g[vv].push_back({uu,w});
}
dijkstra(dists,s);
dijkstra(distu,u);
dijkstra(distv,v);
dfs(t);
long long ans = distu[v];
for (long long i = 1;i <= n;i ++){
if (in[i]){
ans = min(ans,dp[0][i] + distv[i]);
ans = min(ans,dp[1][i] + distu[i]);
}
}
cout<<ans<<'\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
276 ms |
24484 KB |
Output is correct |
2 |
Correct |
278 ms |
24360 KB |
Output is correct |
3 |
Correct |
288 ms |
24596 KB |
Output is correct |
4 |
Correct |
311 ms |
24404 KB |
Output is correct |
5 |
Correct |
271 ms |
24236 KB |
Output is correct |
6 |
Correct |
319 ms |
24548 KB |
Output is correct |
7 |
Correct |
283 ms |
24188 KB |
Output is correct |
8 |
Correct |
280 ms |
24224 KB |
Output is correct |
9 |
Correct |
256 ms |
24180 KB |
Output is correct |
10 |
Correct |
248 ms |
28472 KB |
Output is correct |
11 |
Correct |
190 ms |
19688 KB |
Output is correct |
12 |
Correct |
269 ms |
28416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
362 ms |
24408 KB |
Output is correct |
2 |
Correct |
286 ms |
24348 KB |
Output is correct |
3 |
Correct |
319 ms |
24304 KB |
Output is correct |
4 |
Correct |
281 ms |
24308 KB |
Output is correct |
5 |
Correct |
273 ms |
24280 KB |
Output is correct |
6 |
Correct |
304 ms |
24140 KB |
Output is correct |
7 |
Correct |
293 ms |
24616 KB |
Output is correct |
8 |
Correct |
288 ms |
24272 KB |
Output is correct |
9 |
Correct |
291 ms |
24244 KB |
Output is correct |
10 |
Correct |
285 ms |
24216 KB |
Output is correct |
11 |
Correct |
227 ms |
19440 KB |
Output is correct |
12 |
Correct |
285 ms |
28260 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
6356 KB |
Output is correct |
2 |
Correct |
4 ms |
5076 KB |
Output is correct |
3 |
Correct |
3 ms |
5076 KB |
Output is correct |
4 |
Correct |
17 ms |
8536 KB |
Output is correct |
5 |
Correct |
10 ms |
6740 KB |
Output is correct |
6 |
Correct |
4 ms |
5076 KB |
Output is correct |
7 |
Correct |
4 ms |
5204 KB |
Output is correct |
8 |
Correct |
5 ms |
5332 KB |
Output is correct |
9 |
Correct |
3 ms |
5168 KB |
Output is correct |
10 |
Correct |
8 ms |
6740 KB |
Output is correct |
11 |
Correct |
3 ms |
5032 KB |
Output is correct |
12 |
Correct |
3 ms |
5036 KB |
Output is correct |
13 |
Correct |
3 ms |
5076 KB |
Output is correct |
14 |
Correct |
4 ms |
5044 KB |
Output is correct |
15 |
Correct |
3 ms |
5172 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
276 ms |
24484 KB |
Output is correct |
2 |
Correct |
278 ms |
24360 KB |
Output is correct |
3 |
Correct |
288 ms |
24596 KB |
Output is correct |
4 |
Correct |
311 ms |
24404 KB |
Output is correct |
5 |
Correct |
271 ms |
24236 KB |
Output is correct |
6 |
Correct |
319 ms |
24548 KB |
Output is correct |
7 |
Correct |
283 ms |
24188 KB |
Output is correct |
8 |
Correct |
280 ms |
24224 KB |
Output is correct |
9 |
Correct |
256 ms |
24180 KB |
Output is correct |
10 |
Correct |
248 ms |
28472 KB |
Output is correct |
11 |
Correct |
190 ms |
19688 KB |
Output is correct |
12 |
Correct |
269 ms |
28416 KB |
Output is correct |
13 |
Correct |
362 ms |
24408 KB |
Output is correct |
14 |
Correct |
286 ms |
24348 KB |
Output is correct |
15 |
Correct |
319 ms |
24304 KB |
Output is correct |
16 |
Correct |
281 ms |
24308 KB |
Output is correct |
17 |
Correct |
273 ms |
24280 KB |
Output is correct |
18 |
Correct |
304 ms |
24140 KB |
Output is correct |
19 |
Correct |
293 ms |
24616 KB |
Output is correct |
20 |
Correct |
288 ms |
24272 KB |
Output is correct |
21 |
Correct |
291 ms |
24244 KB |
Output is correct |
22 |
Correct |
285 ms |
24216 KB |
Output is correct |
23 |
Correct |
227 ms |
19440 KB |
Output is correct |
24 |
Correct |
285 ms |
28260 KB |
Output is correct |
25 |
Correct |
12 ms |
6356 KB |
Output is correct |
26 |
Correct |
4 ms |
5076 KB |
Output is correct |
27 |
Correct |
3 ms |
5076 KB |
Output is correct |
28 |
Correct |
17 ms |
8536 KB |
Output is correct |
29 |
Correct |
10 ms |
6740 KB |
Output is correct |
30 |
Correct |
4 ms |
5076 KB |
Output is correct |
31 |
Correct |
4 ms |
5204 KB |
Output is correct |
32 |
Correct |
5 ms |
5332 KB |
Output is correct |
33 |
Correct |
3 ms |
5168 KB |
Output is correct |
34 |
Correct |
8 ms |
6740 KB |
Output is correct |
35 |
Correct |
3 ms |
5032 KB |
Output is correct |
36 |
Correct |
3 ms |
5036 KB |
Output is correct |
37 |
Correct |
3 ms |
5076 KB |
Output is correct |
38 |
Correct |
4 ms |
5044 KB |
Output is correct |
39 |
Correct |
3 ms |
5172 KB |
Output is correct |
40 |
Correct |
284 ms |
28236 KB |
Output is correct |
41 |
Correct |
291 ms |
28624 KB |
Output is correct |
42 |
Correct |
290 ms |
28484 KB |
Output is correct |
43 |
Correct |
186 ms |
20384 KB |
Output is correct |
44 |
Correct |
195 ms |
20396 KB |
Output is correct |
45 |
Correct |
259 ms |
26804 KB |
Output is correct |
46 |
Correct |
259 ms |
27100 KB |
Output is correct |
47 |
Correct |
292 ms |
28168 KB |
Output is correct |
48 |
Correct |
149 ms |
17772 KB |
Output is correct |
49 |
Correct |
230 ms |
27864 KB |
Output is correct |
50 |
Correct |
283 ms |
27592 KB |
Output is correct |
51 |
Correct |
251 ms |
27340 KB |
Output is correct |