#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];
long long dp[100005][2];
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 calcDp0(int p)
{
if(dp[p][0] != 1e18)
return;
dp[p][0] = len[p][1];
for(auto it : v[p])
if(len[p][0] - it.second == len[it.first][0])
{
calcDp0(it.first);
dp[p][0] = min(dp[p][0], dp[it.first][0]);
}
}
void calcDp1(int p)
{
if(dp[p][1] != 1e18)
return;
dp[p][1] = len[p][1];
for(auto it : v[p])
if(len[p][0] + it.second == len[it.first][0] && dp[it.first][0] != 1e18)
{
calcDp1(it.first);
dp[p][1] = min(dp[p][1], dp[it.first][1]);
}
}
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][0] = dp[i][1] = 1e18;
calcDp0(s);
calcDp1(t);
for(int i=1;i<=n;i++)
ans = min(ans, min(dp[i][0], dp[i][1]) + len[i][2]);
cout<<ans;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
588 ms |
24388 KB |
Output is correct |
2 |
Correct |
479 ms |
22828 KB |
Output is correct |
3 |
Correct |
523 ms |
28112 KB |
Output is correct |
4 |
Correct |
601 ms |
23348 KB |
Output is correct |
5 |
Correct |
490 ms |
21980 KB |
Output is correct |
6 |
Correct |
605 ms |
24472 KB |
Output is correct |
7 |
Correct |
492 ms |
22844 KB |
Output is correct |
8 |
Correct |
501 ms |
22844 KB |
Output is correct |
9 |
Correct |
543 ms |
22780 KB |
Output is correct |
10 |
Correct |
508 ms |
22696 KB |
Output is correct |
11 |
Correct |
193 ms |
15732 KB |
Output is correct |
12 |
Correct |
536 ms |
22852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
585 ms |
25428 KB |
Output is correct |
2 |
Correct |
487 ms |
24700 KB |
Output is correct |
3 |
Correct |
486 ms |
24096 KB |
Output is correct |
4 |
Correct |
504 ms |
24496 KB |
Output is correct |
5 |
Correct |
482 ms |
24908 KB |
Output is correct |
6 |
Correct |
520 ms |
27336 KB |
Output is correct |
7 |
Correct |
505 ms |
27168 KB |
Output is correct |
8 |
Correct |
481 ms |
24428 KB |
Output is correct |
9 |
Correct |
499 ms |
24944 KB |
Output is correct |
10 |
Correct |
482 ms |
24052 KB |
Output is correct |
11 |
Correct |
178 ms |
17348 KB |
Output is correct |
12 |
Correct |
522 ms |
27860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
35 ms |
4684 KB |
Output is correct |
2 |
Correct |
2 ms |
2636 KB |
Output is correct |
3 |
Correct |
2 ms |
2636 KB |
Output is correct |
4 |
Correct |
67 ms |
6708 KB |
Output is correct |
5 |
Correct |
31 ms |
4936 KB |
Output is correct |
6 |
Correct |
3 ms |
2764 KB |
Output is correct |
7 |
Correct |
5 ms |
2764 KB |
Output is correct |
8 |
Correct |
6 ms |
2892 KB |
Output is correct |
9 |
Correct |
3 ms |
2764 KB |
Output is correct |
10 |
Correct |
32 ms |
4920 KB |
Output is correct |
11 |
Correct |
2 ms |
2636 KB |
Output is correct |
12 |
Correct |
2 ms |
2636 KB |
Output is correct |
13 |
Correct |
2 ms |
2636 KB |
Output is correct |
14 |
Correct |
3 ms |
2636 KB |
Output is correct |
15 |
Correct |
3 ms |
2636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
588 ms |
24388 KB |
Output is correct |
2 |
Correct |
479 ms |
22828 KB |
Output is correct |
3 |
Correct |
523 ms |
28112 KB |
Output is correct |
4 |
Correct |
601 ms |
23348 KB |
Output is correct |
5 |
Correct |
490 ms |
21980 KB |
Output is correct |
6 |
Correct |
605 ms |
24472 KB |
Output is correct |
7 |
Correct |
492 ms |
22844 KB |
Output is correct |
8 |
Correct |
501 ms |
22844 KB |
Output is correct |
9 |
Correct |
543 ms |
22780 KB |
Output is correct |
10 |
Correct |
508 ms |
22696 KB |
Output is correct |
11 |
Correct |
193 ms |
15732 KB |
Output is correct |
12 |
Correct |
536 ms |
22852 KB |
Output is correct |
13 |
Correct |
585 ms |
25428 KB |
Output is correct |
14 |
Correct |
487 ms |
24700 KB |
Output is correct |
15 |
Correct |
486 ms |
24096 KB |
Output is correct |
16 |
Correct |
504 ms |
24496 KB |
Output is correct |
17 |
Correct |
482 ms |
24908 KB |
Output is correct |
18 |
Correct |
520 ms |
27336 KB |
Output is correct |
19 |
Correct |
505 ms |
27168 KB |
Output is correct |
20 |
Correct |
481 ms |
24428 KB |
Output is correct |
21 |
Correct |
499 ms |
24944 KB |
Output is correct |
22 |
Correct |
482 ms |
24052 KB |
Output is correct |
23 |
Correct |
178 ms |
17348 KB |
Output is correct |
24 |
Correct |
522 ms |
27860 KB |
Output is correct |
25 |
Correct |
35 ms |
4684 KB |
Output is correct |
26 |
Correct |
2 ms |
2636 KB |
Output is correct |
27 |
Correct |
2 ms |
2636 KB |
Output is correct |
28 |
Correct |
67 ms |
6708 KB |
Output is correct |
29 |
Correct |
31 ms |
4936 KB |
Output is correct |
30 |
Correct |
3 ms |
2764 KB |
Output is correct |
31 |
Correct |
5 ms |
2764 KB |
Output is correct |
32 |
Correct |
6 ms |
2892 KB |
Output is correct |
33 |
Correct |
3 ms |
2764 KB |
Output is correct |
34 |
Correct |
32 ms |
4920 KB |
Output is correct |
35 |
Correct |
2 ms |
2636 KB |
Output is correct |
36 |
Correct |
2 ms |
2636 KB |
Output is correct |
37 |
Correct |
2 ms |
2636 KB |
Output is correct |
38 |
Correct |
3 ms |
2636 KB |
Output is correct |
39 |
Correct |
3 ms |
2636 KB |
Output is correct |
40 |
Correct |
667 ms |
26216 KB |
Output is correct |
41 |
Correct |
602 ms |
25076 KB |
Output is correct |
42 |
Correct |
601 ms |
24900 KB |
Output is correct |
43 |
Correct |
222 ms |
18456 KB |
Output is correct |
44 |
Correct |
203 ms |
18520 KB |
Output is correct |
45 |
Correct |
499 ms |
23960 KB |
Output is correct |
46 |
Correct |
503 ms |
23748 KB |
Output is correct |
47 |
Correct |
580 ms |
26656 KB |
Output is correct |
48 |
Correct |
182 ms |
15472 KB |
Output is correct |
49 |
Correct |
590 ms |
27432 KB |
Output is correct |
50 |
Correct |
479 ms |
24336 KB |
Output is correct |
51 |
Correct |
493 ms |
24008 KB |
Output is correct |