#include<bits/stdc++.h>
using namespace std;
struct point{
int64_t u,pp,bb;
};
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int64_t n,m;cin>>n>>m;
int64_t S,T;cin>>S>>T;
--S;--T;
int64_t U,V;cin>>U>>V;
--U;--V;
vector<vector<pair<int64_t,int64_t>>>adj(n);
for (int64_t i = 0;i<m;++i){
int64_t x,y,z;cin>>x>>y>>z;
--x;--y;
adj[x].push_back({y,z});
adj[y].push_back({x,z});
}
const int64_t mxn = 1e18;
priority_queue<pair<int64_t,pair<int64_t,int64_t>>>q;
vector<vector<int64_t>>dist(n,vector<int64_t>(2,mxn));
q.push({0,{U,0}});
q.push({0,{V,1}});
dist[U][0] = 0;
dist[V][1] = 0;
while(!q.empty()){
auto u = q.top().second;
q.pop();
for (auto x:adj[u.first]){
if (dist[x.first][u.second] > dist[u.first][u.second] + x.second){
dist[x.first][u.second] = dist[u.first][u.second] + x.second;
q.push({-dist[x.first][u.second],{x.first,u.second}});
}
}
}
int64_t ans = dist[U][1];
vector<int64_t>dis(n,mxn);
priority_queue<pair<long long,long long>>qs;
qs.push({0,S});
dis[S] = 0;
vector<vector<int64_t>>dp(n,vector<int64_t>(4,mxn));
while(!qs.empty()){
auto u = qs.top();
qs.pop();
if (-u.first > dis[u.second])continue;
for (auto x:adj[u.second]){
if (dis[x.first] > dis[u.second] + x.second){
dis[x.first] = dis[u.second] + x.second;
qs.push({-dis[x.first],x.first});
}
}
}
dp[S][1] = dist[S][0];
dp[S][2] = dist[S][1];
vector<bool>visited(n,false);
dp[S][3] = dist[S][0] + dist[S][1];
dp[S][0] = 0;
auto bfs = [&](){
set<pair<int64_t,int64_t>>qq;
qq.insert({0,S});
while(!qq.empty()){
auto vv = *qq.begin();
qq.erase(qq.begin());
auto u = vv.second;
visited[u] = true;
for (auto x:adj[u]){
if (dis[x.first] == dis[u] + x.second && !visited[x.first]){
qq.insert({dis[x.first],x.first});
auto get = [&](int64_t v,int64_t j){
int64_t res = 0;
if (j & 1)res+=dist[v][0];
if (j & 2)res+=dist[v][1];
return res;
};
for (int i = 0;i < 4;++i){
for (int j = 0;j<4;++j){
dp[x.first][i | j] = min(dp[x.first][i | j],dp[u][i] + get(x.first,j));
}
}
}
}
}
ans = min(ans,dp[T][3]);
};
bfs();
cout<<ans<<'\n';
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
432 ms |
31292 KB |
Output is correct |
2 |
Correct |
441 ms |
30100 KB |
Output is correct |
3 |
Correct |
357 ms |
29128 KB |
Output is correct |
4 |
Correct |
469 ms |
31336 KB |
Output is correct |
5 |
Correct |
465 ms |
33392 KB |
Output is correct |
6 |
Correct |
469 ms |
35244 KB |
Output is correct |
7 |
Correct |
463 ms |
33372 KB |
Output is correct |
8 |
Correct |
443 ms |
32604 KB |
Output is correct |
9 |
Correct |
471 ms |
32628 KB |
Output is correct |
10 |
Correct |
412 ms |
32564 KB |
Output is correct |
11 |
Correct |
161 ms |
22936 KB |
Output is correct |
12 |
Correct |
479 ms |
32272 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
482 ms |
30568 KB |
Output is correct |
2 |
Correct |
395 ms |
29976 KB |
Output is correct |
3 |
Correct |
434 ms |
29988 KB |
Output is correct |
4 |
Correct |
435 ms |
30008 KB |
Output is correct |
5 |
Correct |
409 ms |
29984 KB |
Output is correct |
6 |
Correct |
366 ms |
29184 KB |
Output is correct |
7 |
Correct |
444 ms |
29908 KB |
Output is correct |
8 |
Correct |
398 ms |
30044 KB |
Output is correct |
9 |
Correct |
399 ms |
30160 KB |
Output is correct |
10 |
Correct |
445 ms |
30180 KB |
Output is correct |
11 |
Correct |
163 ms |
20912 KB |
Output is correct |
12 |
Correct |
392 ms |
29272 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
1620 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
16 ms |
3796 KB |
Output is correct |
5 |
Correct |
8 ms |
2004 KB |
Output is correct |
6 |
Correct |
2 ms |
468 KB |
Output is correct |
7 |
Correct |
2 ms |
516 KB |
Output is correct |
8 |
Correct |
2 ms |
584 KB |
Output is correct |
9 |
Correct |
2 ms |
468 KB |
Output is correct |
10 |
Correct |
7 ms |
2004 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
328 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
432 ms |
31292 KB |
Output is correct |
2 |
Correct |
441 ms |
30100 KB |
Output is correct |
3 |
Correct |
357 ms |
29128 KB |
Output is correct |
4 |
Correct |
469 ms |
31336 KB |
Output is correct |
5 |
Correct |
465 ms |
33392 KB |
Output is correct |
6 |
Correct |
469 ms |
35244 KB |
Output is correct |
7 |
Correct |
463 ms |
33372 KB |
Output is correct |
8 |
Correct |
443 ms |
32604 KB |
Output is correct |
9 |
Correct |
471 ms |
32628 KB |
Output is correct |
10 |
Correct |
412 ms |
32564 KB |
Output is correct |
11 |
Correct |
161 ms |
22936 KB |
Output is correct |
12 |
Correct |
479 ms |
32272 KB |
Output is correct |
13 |
Correct |
482 ms |
30568 KB |
Output is correct |
14 |
Correct |
395 ms |
29976 KB |
Output is correct |
15 |
Correct |
434 ms |
29988 KB |
Output is correct |
16 |
Correct |
435 ms |
30008 KB |
Output is correct |
17 |
Correct |
409 ms |
29984 KB |
Output is correct |
18 |
Correct |
366 ms |
29184 KB |
Output is correct |
19 |
Correct |
444 ms |
29908 KB |
Output is correct |
20 |
Correct |
398 ms |
30044 KB |
Output is correct |
21 |
Correct |
399 ms |
30160 KB |
Output is correct |
22 |
Correct |
445 ms |
30180 KB |
Output is correct |
23 |
Correct |
163 ms |
20912 KB |
Output is correct |
24 |
Correct |
392 ms |
29272 KB |
Output is correct |
25 |
Correct |
8 ms |
1620 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
340 KB |
Output is correct |
28 |
Correct |
16 ms |
3796 KB |
Output is correct |
29 |
Correct |
8 ms |
2004 KB |
Output is correct |
30 |
Correct |
2 ms |
468 KB |
Output is correct |
31 |
Correct |
2 ms |
516 KB |
Output is correct |
32 |
Correct |
2 ms |
584 KB |
Output is correct |
33 |
Correct |
2 ms |
468 KB |
Output is correct |
34 |
Correct |
7 ms |
2004 KB |
Output is correct |
35 |
Correct |
1 ms |
340 KB |
Output is correct |
36 |
Correct |
1 ms |
328 KB |
Output is correct |
37 |
Correct |
1 ms |
340 KB |
Output is correct |
38 |
Correct |
1 ms |
340 KB |
Output is correct |
39 |
Correct |
1 ms |
340 KB |
Output is correct |
40 |
Correct |
406 ms |
36368 KB |
Output is correct |
41 |
Correct |
397 ms |
33504 KB |
Output is correct |
42 |
Correct |
421 ms |
33504 KB |
Output is correct |
43 |
Correct |
198 ms |
23020 KB |
Output is correct |
44 |
Correct |
202 ms |
23036 KB |
Output is correct |
45 |
Correct |
472 ms |
32864 KB |
Output is correct |
46 |
Correct |
447 ms |
32972 KB |
Output is correct |
47 |
Correct |
489 ms |
36556 KB |
Output is correct |
48 |
Correct |
235 ms |
22432 KB |
Output is correct |
49 |
Correct |
458 ms |
41320 KB |
Output is correct |
50 |
Correct |
421 ms |
31256 KB |
Output is correct |
51 |
Correct |
399 ms |
31836 KB |
Output is correct |