#include <bits/stdc++.h>
using namespace std;
long long n,m,s,t,a,b,ans;
vector<pair<long long, long long>> v[100005];
long long len[100005][4];
pair<long long, long long> dp[100005];
void djikstra(int s, int nr)
{
for(int i=1;i<=n;i++)
len[i][nr] = 1e18;
multiset<pair<long long, long long>> mul;
mul.insert({0, s});
while(!mul.empty())
{
long long p = mul.begin()->second;
long long val = mul.begin()->first;
mul.erase(mul.begin());
if(len[p][nr] != 1e18)
continue;
len[p][nr] = val;
for(auto it : v[p])
{
if(len[it.first][nr] != 1e18)
continue;
mul.insert({val + it.second, it.first});
}
}
}
void calcDp(int p)
{
if(dp[p] != make_pair((long long)1e18, (long long)1e18))
return;
dp[p] = {len[p][1], len[p][2]};
for(auto it : v[p])
if(len[p][0] - it.second == len[it.first][0])
{
calcDp(it.first);
dp[p].first = min(dp[p].first, dp[it.first].first);
dp[p].second = min(dp[p].second, dp[it.first].second);
}
ans=min(ans, dp[p].first + dp[p].second);
}
int main()
{
cin>>n>>m>>s>>t>>a>>b;
for(int i=1;i<=m;i++)
{
int x, y, c;
cin>>x>>y>>c;
v[x].push_back({y, c});
v[y].push_back({x, c});
}
djikstra(t, 0);
djikstra(b, 1);
djikstra(a, 2);
ans = len[a][1];
for(int i=1;i<=n;i++)
dp[i] = {1e18, 1e18};
calcDp(s);
cout<<ans;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
586 ms |
24380 KB |
Output is correct |
2 |
Correct |
490 ms |
23940 KB |
Output is correct |
3 |
Correct |
536 ms |
29140 KB |
Output is correct |
4 |
Correct |
597 ms |
24516 KB |
Output is correct |
5 |
Correct |
481 ms |
23064 KB |
Output is correct |
6 |
Correct |
658 ms |
25616 KB |
Output is correct |
7 |
Correct |
527 ms |
24052 KB |
Output is correct |
8 |
Correct |
487 ms |
23972 KB |
Output is correct |
9 |
Correct |
537 ms |
23768 KB |
Output is correct |
10 |
Correct |
577 ms |
23952 KB |
Output is correct |
11 |
Correct |
170 ms |
16836 KB |
Output is correct |
12 |
Correct |
480 ms |
23968 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
557 ms |
25456 KB |
Output is correct |
2 |
Correct |
504 ms |
25712 KB |
Output is correct |
3 |
Correct |
483 ms |
25208 KB |
Output is correct |
4 |
Correct |
473 ms |
25564 KB |
Output is correct |
5 |
Correct |
486 ms |
25652 KB |
Output is correct |
6 |
Correct |
535 ms |
28040 KB |
Output is correct |
7 |
Correct |
515 ms |
27972 KB |
Output is correct |
8 |
Correct |
493 ms |
25196 KB |
Output is correct |
9 |
Correct |
476 ms |
25820 KB |
Output is correct |
10 |
Correct |
488 ms |
24892 KB |
Output is correct |
11 |
Correct |
172 ms |
18120 KB |
Output is correct |
12 |
Correct |
533 ms |
28624 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
4684 KB |
Output is correct |
2 |
Correct |
2 ms |
2636 KB |
Output is correct |
3 |
Incorrect |
3 ms |
2636 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
586 ms |
24380 KB |
Output is correct |
2 |
Correct |
490 ms |
23940 KB |
Output is correct |
3 |
Correct |
536 ms |
29140 KB |
Output is correct |
4 |
Correct |
597 ms |
24516 KB |
Output is correct |
5 |
Correct |
481 ms |
23064 KB |
Output is correct |
6 |
Correct |
658 ms |
25616 KB |
Output is correct |
7 |
Correct |
527 ms |
24052 KB |
Output is correct |
8 |
Correct |
487 ms |
23972 KB |
Output is correct |
9 |
Correct |
537 ms |
23768 KB |
Output is correct |
10 |
Correct |
577 ms |
23952 KB |
Output is correct |
11 |
Correct |
170 ms |
16836 KB |
Output is correct |
12 |
Correct |
480 ms |
23968 KB |
Output is correct |
13 |
Correct |
557 ms |
25456 KB |
Output is correct |
14 |
Correct |
504 ms |
25712 KB |
Output is correct |
15 |
Correct |
483 ms |
25208 KB |
Output is correct |
16 |
Correct |
473 ms |
25564 KB |
Output is correct |
17 |
Correct |
486 ms |
25652 KB |
Output is correct |
18 |
Correct |
535 ms |
28040 KB |
Output is correct |
19 |
Correct |
515 ms |
27972 KB |
Output is correct |
20 |
Correct |
493 ms |
25196 KB |
Output is correct |
21 |
Correct |
476 ms |
25820 KB |
Output is correct |
22 |
Correct |
488 ms |
24892 KB |
Output is correct |
23 |
Correct |
172 ms |
18120 KB |
Output is correct |
24 |
Correct |
533 ms |
28624 KB |
Output is correct |
25 |
Correct |
34 ms |
4684 KB |
Output is correct |
26 |
Correct |
2 ms |
2636 KB |
Output is correct |
27 |
Incorrect |
3 ms |
2636 KB |
Output isn't correct |
28 |
Halted |
0 ms |
0 KB |
- |