#include <bits/stdc++.h>
#define MAX 101000
bool rota[MAX];
typedef std::pair<long long,long long> pii;
typedef std::pair<long long,pii> pip;
std::vector<long long> veio[MAX];
std::map<long long,bool> mapa[MAX];
std::vector<long long> levou[MAX];
std::vector<pii> con[MAX];
bool dp_check[MAX],dp_res[MAX];
long long S,T,U,V;
bool dp(int x){
if(dp_check[x])return dp_res[x];
dp_check[x]=true;
for(auto&z:veio[x]){
if(dp(z)){
dp_res[x]=rota[x]=true;
}
}
return dp_res[x];
}
long long valextra[MAX],pesmin[MAX];
long long inf =1000000000000000000LL;
long long dpb[MAX],dpu[MAX],cup[MAX],cbai[MAX];
long long dpbai(int x) {
if(cbai[x])return dpb[x];
dpb[x]=inf;
cbai[x]=true;
long long min = pesmin[x];
for(auto&z:veio[x]) {
if(rota[z])
min=std::min(min,dpbai(z));
}
return dpb[x]=min;
}
long long dpup(int x) {
if(cup[x])return dpu[x];
dpu[x]=inf;
cup[x]=true;
long long min = pesmin[x];
for(auto&z:levou[x]) {
if(rota[z]&&mapa[x].find(z)==mapa[x].end())
min=std::min(min,dpup(z));
}
return dpu[x]=min;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int N,M;
std::cin>>N>>M;
std::cin>>S>>T>>U>>V;--S;--T;--U;--V;
for(int i=0;i!=M;++i){
long long a,b,c;
std::cin>>a>>b>>c;--a;--b;
con[a].push_back({b,c});
con[b].push_back({a,c});
}
///Rotas
{
bool visitou[N]={};
long long custos[N]={};for(auto&x:custos)x=inf;
std::priority_queue<pip,std::vector<pip>,std::greater<pip>> queue;
queue.push({0LL,{S,S}});
while(queue.size()){
auto _ = queue.top();
queue.pop();
auto custo = _.first;
auto atual = _.second.first;
auto prev = _.second.second;
if(custos[atual]>=custo){
veio[atual].push_back(prev);
mapa[atual][prev]=true;
levou[prev].push_back(atual);
}
if(visitou[atual])continue;
visitou[atual]=true;
custos[atual]=custo;
for(auto&x:con[atual]){
queue.push({custo+x.second,{x.first,atual}});
}
}
dp_res[S]=dp_check[S]=rota[S]=true;
dp(T);
}
///Peso Minimo para V
{
bool visitou[N]={};
std::priority_queue<pii,std::vector<pii>,std::greater<pii>> queue;
queue.push({0LL,V});
while(queue.size()){
auto _ = queue.top();
queue.pop();
auto custo = _.first;
auto atual = _.second;
if(visitou[atual])continue;
visitou[atual]=true;
pesmin[atual]=custo;
for(auto&x:con[atual]){
queue.push({custo+x.second,x.first});
}
}
}
///Caminhos Minimos (2 DPs)
{
for(int i=0;i!=N;++i){
if(rota[i]){
valextra[i]=std::min(dpup(i),dpbai(i));
}
}
}
bool visitou[N]={};
std::priority_queue<pii,std::vector<pii>,std::greater<pii>> queue;
queue.push({0LL,U});
while(queue.size()){
auto _ = queue.top();
queue.pop();
auto custo = _.first;
auto atual = _.second;
if(visitou[atual])continue;
visitou[atual]=true;
if(atual==V){
std::cout<<custo<<"\n";
return 0;
}
if(rota[atual]){
queue.push({custo+valextra[atual],V});
}
for(auto&x:con[atual]){
queue.push({custo+x.second,x.first});
}
}
assert(0);
std::cout<<"-1\n";
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
597 ms |
43480 KB |
Output is correct |
2 |
Correct |
513 ms |
47344 KB |
Output is correct |
3 |
Correct |
601 ms |
54284 KB |
Output is correct |
4 |
Correct |
646 ms |
50412 KB |
Output is correct |
5 |
Correct |
558 ms |
52824 KB |
Output is correct |
6 |
Correct |
599 ms |
45780 KB |
Output is correct |
7 |
Correct |
560 ms |
53792 KB |
Output is correct |
8 |
Correct |
514 ms |
54168 KB |
Output is correct |
9 |
Correct |
508 ms |
46200 KB |
Output is correct |
10 |
Correct |
482 ms |
46796 KB |
Output is correct |
11 |
Correct |
278 ms |
41284 KB |
Output is correct |
12 |
Correct |
531 ms |
47132 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
509 ms |
47692 KB |
Output is correct |
2 |
Correct |
553 ms |
48768 KB |
Output is correct |
3 |
Correct |
563 ms |
48672 KB |
Output is correct |
4 |
Correct |
489 ms |
48548 KB |
Output is correct |
5 |
Correct |
503 ms |
49128 KB |
Output is correct |
6 |
Correct |
616 ms |
54192 KB |
Output is correct |
7 |
Correct |
494 ms |
52080 KB |
Output is correct |
8 |
Correct |
486 ms |
48632 KB |
Output is correct |
9 |
Correct |
490 ms |
49484 KB |
Output is correct |
10 |
Correct |
521 ms |
48540 KB |
Output is correct |
11 |
Correct |
277 ms |
42612 KB |
Output is correct |
12 |
Correct |
570 ms |
54252 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
37 ms |
15144 KB |
Output is correct |
2 |
Correct |
9 ms |
12336 KB |
Output is correct |
3 |
Correct |
10 ms |
12236 KB |
Output is correct |
4 |
Correct |
75 ms |
18560 KB |
Output is correct |
5 |
Correct |
35 ms |
15204 KB |
Output is correct |
6 |
Correct |
11 ms |
12432 KB |
Output is correct |
7 |
Correct |
11 ms |
12492 KB |
Output is correct |
8 |
Correct |
12 ms |
12620 KB |
Output is correct |
9 |
Correct |
11 ms |
12416 KB |
Output is correct |
10 |
Correct |
39 ms |
15568 KB |
Output is correct |
11 |
Correct |
9 ms |
12316 KB |
Output is correct |
12 |
Correct |
9 ms |
12252 KB |
Output is correct |
13 |
Correct |
9 ms |
12236 KB |
Output is correct |
14 |
Correct |
10 ms |
12312 KB |
Output is correct |
15 |
Correct |
10 ms |
12364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
597 ms |
43480 KB |
Output is correct |
2 |
Correct |
513 ms |
47344 KB |
Output is correct |
3 |
Correct |
601 ms |
54284 KB |
Output is correct |
4 |
Correct |
646 ms |
50412 KB |
Output is correct |
5 |
Correct |
558 ms |
52824 KB |
Output is correct |
6 |
Correct |
599 ms |
45780 KB |
Output is correct |
7 |
Correct |
560 ms |
53792 KB |
Output is correct |
8 |
Correct |
514 ms |
54168 KB |
Output is correct |
9 |
Correct |
508 ms |
46200 KB |
Output is correct |
10 |
Correct |
482 ms |
46796 KB |
Output is correct |
11 |
Correct |
278 ms |
41284 KB |
Output is correct |
12 |
Correct |
531 ms |
47132 KB |
Output is correct |
13 |
Correct |
509 ms |
47692 KB |
Output is correct |
14 |
Correct |
553 ms |
48768 KB |
Output is correct |
15 |
Correct |
563 ms |
48672 KB |
Output is correct |
16 |
Correct |
489 ms |
48548 KB |
Output is correct |
17 |
Correct |
503 ms |
49128 KB |
Output is correct |
18 |
Correct |
616 ms |
54192 KB |
Output is correct |
19 |
Correct |
494 ms |
52080 KB |
Output is correct |
20 |
Correct |
486 ms |
48632 KB |
Output is correct |
21 |
Correct |
490 ms |
49484 KB |
Output is correct |
22 |
Correct |
521 ms |
48540 KB |
Output is correct |
23 |
Correct |
277 ms |
42612 KB |
Output is correct |
24 |
Correct |
570 ms |
54252 KB |
Output is correct |
25 |
Correct |
37 ms |
15144 KB |
Output is correct |
26 |
Correct |
9 ms |
12336 KB |
Output is correct |
27 |
Correct |
10 ms |
12236 KB |
Output is correct |
28 |
Correct |
75 ms |
18560 KB |
Output is correct |
29 |
Correct |
35 ms |
15204 KB |
Output is correct |
30 |
Correct |
11 ms |
12432 KB |
Output is correct |
31 |
Correct |
11 ms |
12492 KB |
Output is correct |
32 |
Correct |
12 ms |
12620 KB |
Output is correct |
33 |
Correct |
11 ms |
12416 KB |
Output is correct |
34 |
Correct |
39 ms |
15568 KB |
Output is correct |
35 |
Correct |
9 ms |
12316 KB |
Output is correct |
36 |
Correct |
9 ms |
12252 KB |
Output is correct |
37 |
Correct |
9 ms |
12236 KB |
Output is correct |
38 |
Correct |
10 ms |
12312 KB |
Output is correct |
39 |
Correct |
10 ms |
12364 KB |
Output is correct |
40 |
Correct |
564 ms |
44884 KB |
Output is correct |
41 |
Correct |
522 ms |
46076 KB |
Output is correct |
42 |
Correct |
547 ms |
46232 KB |
Output is correct |
43 |
Correct |
293 ms |
41132 KB |
Output is correct |
44 |
Correct |
275 ms |
40896 KB |
Output is correct |
45 |
Correct |
636 ms |
56140 KB |
Output is correct |
46 |
Correct |
625 ms |
53524 KB |
Output is correct |
47 |
Correct |
603 ms |
52956 KB |
Output is correct |
48 |
Correct |
286 ms |
39224 KB |
Output is correct |
49 |
Correct |
632 ms |
52048 KB |
Output is correct |
50 |
Correct |
614 ms |
54000 KB |
Output is correct |
51 |
Correct |
617 ms |
56444 KB |
Output is correct |