#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define x first
#define y second
vector<vector<ll>> v(5,vector<ll>(100001,1e16));
vector<vector<pair<ll,ll>>>G1(100001);
vector<vector<ll>>G2(100001);
void dijkstra(ll pl, ll node)
{
priority_queue<pair<ll,ll>> q;
q.push({0,node});
while(!q.empty())
{
pair<ll,ll> a=q.top();q.pop();
if(v[pl][a.y]==1e16)
{
v[pl][a.y]=-a.x;
for(auto i:G1[a.y])
if(v[pl][i.x]==1e16)
q.push({a.x-i.y,i.x});
}
}
}
vector<pair<ll,pair<ll,ll>>> dp(100001,{-1,{0,0}});
pair<ll,pair<ll,ll>> dfs(ll node, ll padre)
{
if(dp[node].first!=-1)
return dp[node];
pair<ll,pair<ll,ll>> sol={v[2][node]+v[3][node],{v[2][node],v[3][node]}};
for(auto i:G2[node])
{
if(i!=padre)
{
pair<ll,pair<ll,ll>> temp=dfs(i,node);
sol.x=min(sol.x,temp.x);
sol.x=min(sol.x,v[2][node]+temp.y.y);
sol.x=min(sol.x,v[3][node]+temp.y.x);
sol.y.x=min(sol.y.x,temp.y.x);
sol.y.y=min(sol.y.y,temp.y.y);
}
}
return dp[node]=sol;
}
int main()
{
ll n,m;
cin>>n>>m;
ll s,t,u,w;
cin>>s>>t>>u>>w;
for(int i=0; i<m; i++)
{
ll a,b,c;
cin>>a>>b>>c;
G1[a].push_back({b,c});
G1[b].push_back({a,c});
}
dijkstra(0,s);
dijkstra(1,t);
dijkstra(2,u);
dijkstra(3,w);
for(int i=1; i<=n; i++)
for(auto j:G1[i])
if(v[0][i]+v[1][j.x]+j.y==v[0][t])
G2[i].push_back(j.x);
cout<<min(dfs(s,0).x,v[2][w]);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
341 ms |
25744 KB |
Output is correct |
2 |
Correct |
359 ms |
25208 KB |
Output is correct |
3 |
Correct |
326 ms |
36076 KB |
Output is correct |
4 |
Correct |
400 ms |
29168 KB |
Output is correct |
5 |
Correct |
336 ms |
29228 KB |
Output is correct |
6 |
Correct |
334 ms |
29392 KB |
Output is correct |
7 |
Correct |
344 ms |
28468 KB |
Output is correct |
8 |
Correct |
345 ms |
28480 KB |
Output is correct |
9 |
Correct |
358 ms |
29928 KB |
Output is correct |
10 |
Correct |
349 ms |
29568 KB |
Output is correct |
11 |
Correct |
147 ms |
25796 KB |
Output is correct |
12 |
Correct |
336 ms |
29432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
387 ms |
26060 KB |
Output is correct |
2 |
Correct |
312 ms |
26456 KB |
Output is correct |
3 |
Correct |
354 ms |
25412 KB |
Output is correct |
4 |
Correct |
314 ms |
28172 KB |
Output is correct |
5 |
Correct |
324 ms |
27584 KB |
Output is correct |
6 |
Correct |
323 ms |
31276 KB |
Output is correct |
7 |
Correct |
363 ms |
32556 KB |
Output is correct |
8 |
Correct |
310 ms |
26356 KB |
Output is correct |
9 |
Correct |
329 ms |
27356 KB |
Output is correct |
10 |
Correct |
328 ms |
25596 KB |
Output is correct |
11 |
Correct |
128 ms |
26936 KB |
Output is correct |
12 |
Correct |
370 ms |
31840 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
13128 KB |
Output is correct |
2 |
Correct |
5 ms |
11340 KB |
Output is correct |
3 |
Correct |
6 ms |
11340 KB |
Output is correct |
4 |
Correct |
54 ms |
15780 KB |
Output is correct |
5 |
Correct |
34 ms |
13892 KB |
Output is correct |
6 |
Correct |
8 ms |
11336 KB |
Output is correct |
7 |
Correct |
7 ms |
11592 KB |
Output is correct |
8 |
Correct |
8 ms |
11592 KB |
Output is correct |
9 |
Correct |
6 ms |
11336 KB |
Output is correct |
10 |
Correct |
29 ms |
13900 KB |
Output is correct |
11 |
Correct |
6 ms |
11336 KB |
Output is correct |
12 |
Correct |
5 ms |
11340 KB |
Output is correct |
13 |
Correct |
5 ms |
11340 KB |
Output is correct |
14 |
Correct |
6 ms |
11432 KB |
Output is correct |
15 |
Correct |
7 ms |
11336 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
341 ms |
25744 KB |
Output is correct |
2 |
Correct |
359 ms |
25208 KB |
Output is correct |
3 |
Correct |
326 ms |
36076 KB |
Output is correct |
4 |
Correct |
400 ms |
29168 KB |
Output is correct |
5 |
Correct |
336 ms |
29228 KB |
Output is correct |
6 |
Correct |
334 ms |
29392 KB |
Output is correct |
7 |
Correct |
344 ms |
28468 KB |
Output is correct |
8 |
Correct |
345 ms |
28480 KB |
Output is correct |
9 |
Correct |
358 ms |
29928 KB |
Output is correct |
10 |
Correct |
349 ms |
29568 KB |
Output is correct |
11 |
Correct |
147 ms |
25796 KB |
Output is correct |
12 |
Correct |
336 ms |
29432 KB |
Output is correct |
13 |
Correct |
387 ms |
26060 KB |
Output is correct |
14 |
Correct |
312 ms |
26456 KB |
Output is correct |
15 |
Correct |
354 ms |
25412 KB |
Output is correct |
16 |
Correct |
314 ms |
28172 KB |
Output is correct |
17 |
Correct |
324 ms |
27584 KB |
Output is correct |
18 |
Correct |
323 ms |
31276 KB |
Output is correct |
19 |
Correct |
363 ms |
32556 KB |
Output is correct |
20 |
Correct |
310 ms |
26356 KB |
Output is correct |
21 |
Correct |
329 ms |
27356 KB |
Output is correct |
22 |
Correct |
328 ms |
25596 KB |
Output is correct |
23 |
Correct |
128 ms |
26936 KB |
Output is correct |
24 |
Correct |
370 ms |
31840 KB |
Output is correct |
25 |
Correct |
29 ms |
13128 KB |
Output is correct |
26 |
Correct |
5 ms |
11340 KB |
Output is correct |
27 |
Correct |
6 ms |
11340 KB |
Output is correct |
28 |
Correct |
54 ms |
15780 KB |
Output is correct |
29 |
Correct |
34 ms |
13892 KB |
Output is correct |
30 |
Correct |
8 ms |
11336 KB |
Output is correct |
31 |
Correct |
7 ms |
11592 KB |
Output is correct |
32 |
Correct |
8 ms |
11592 KB |
Output is correct |
33 |
Correct |
6 ms |
11336 KB |
Output is correct |
34 |
Correct |
29 ms |
13900 KB |
Output is correct |
35 |
Correct |
6 ms |
11336 KB |
Output is correct |
36 |
Correct |
5 ms |
11340 KB |
Output is correct |
37 |
Correct |
5 ms |
11340 KB |
Output is correct |
38 |
Correct |
6 ms |
11432 KB |
Output is correct |
39 |
Correct |
7 ms |
11336 KB |
Output is correct |
40 |
Correct |
357 ms |
29100 KB |
Output is correct |
41 |
Correct |
342 ms |
29376 KB |
Output is correct |
42 |
Correct |
396 ms |
29524 KB |
Output is correct |
43 |
Correct |
144 ms |
28480 KB |
Output is correct |
44 |
Correct |
130 ms |
28624 KB |
Output is correct |
45 |
Correct |
352 ms |
28232 KB |
Output is correct |
46 |
Correct |
341 ms |
27816 KB |
Output is correct |
47 |
Correct |
359 ms |
28920 KB |
Output is correct |
48 |
Correct |
126 ms |
23300 KB |
Output is correct |
49 |
Correct |
311 ms |
28520 KB |
Output is correct |
50 |
Correct |
359 ms |
27196 KB |
Output is correct |
51 |
Correct |
340 ms |
28076 KB |
Output is correct |