#include <bits/stdc++.h>
#define maxn 100005
#define pii pair<int,int>
#define INF 100000000000000000
using namespace std;
int n,m;
vector<pii>adj[maxn];
int s,t;
long long ds[maxn];
long long dt[maxn];
long long duu[maxn];
int u,v;
long long du[maxn][3];
int first[maxn];
//0 nije poceo
//1 traje
//2 prosao
vector<int>mv[3];
priority_queue<pair<long long,int>>pq;
priority_queue<pair<long long,pii>>pq2;
long long manji(long long aa,long long bb)
{
if(aa<bb)return aa;
return bb;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
mv[0].push_back(0);
mv[0].push_back(1);
mv[1].push_back(1);
mv[1].push_back(2);
mv[2].push_back(2);
cin>>n>>m;
cin>>s>>t;
cin>>u>>v;
for(int i=0;i<m;i++)
{
int x,y,c;
cin>>x>>y>>c;
adj[x].push_back({y,c});
adj[y].push_back({x,c});
}
//cout<<endl;
for(int i=1;i<=n;i++)ds[i]=INF;
pq.push({0LL,s});
ds[s]=0LL;
while(!pq.empty())
{
int x=pq.top().second;
pq.pop();
for(auto zz:adj[x])
{
int y=zz.first;
int ras=zz.second;
if(ds[y]>ds[x]+ras)
{
ds[y]=ds[x]+ras;
pq.push({-ds[y],y});
}
}
}
//for(int i=1;i<=n;i++)cout<<i<<" "<<ds[i]<<endl;cout<<endl;
for(int i=1;i<=n;i++)dt[i]=INF;
pq.push({0LL,t});
dt[t]=0LL;
while(!pq.empty())
{
int x=pq.top().second;
pq.pop();
for(auto zz:adj[x])
{
int y=zz.first;
int ras=zz.second;
if(dt[y]>dt[x]+ras)
{
dt[y]=dt[x]+ras;
pq.push({-dt[y],y});
}
}
}
//for(int i=1;i<=n;i++)cout<<i<<" "<<dt[i]<<endl;cout<<endl;
for(int i=1;i<=n;i++)duu[i]=INF;
pq.push({0LL,u});
duu[u]=0LL;
while(!pq.empty())
{
int x=pq.top().second;
pq.pop();
for(auto zz:adj[x])
{
int y=zz.first;
int ras=zz.second;
if(duu[y]>duu[x]+ras)
{
duu[y]=duu[x]+ras;
pq.push({-duu[y],y});
}
}
}
//for(int i=1;i<=n;i++)cout<<i<<" "<<duu[i]<<endl;cout<<endl;
for(int i=1;i<=n;i++)du[i][0]=du[i][1]=du[i][2]=INF;
pq2.push({0LL,{u,0}});
pq2.push({0LL,{u,2}});
du[u][0]=0LL;
du[u][2]=0LL;
du[u][1]=0LL;
first[u]=u;
if(ds[u]+dt[u]!=ds[t])du[u][1]=INF;
pq2.push({-du[u][1],{u,1}});
while(!pq2.empty())
{
int x=pq2.top().second.first;
int ty=pq2.top().second.second;
pq2.pop();
for(auto zz:adj[x])
{
int y=zz.first;
for(auto tt:mv[ty])
{
int ras=zz.second;
int prvi=first[x];
if(ty!=1)prvi=x;
if(tt==1)
{
//if(x==2 && ty==0 && y==1 && tt==1)cout<<"qrac1 "<<y<<" "<<prvi<<" "<<ds[prvi]<<" "<<dt[y]<<" "<<duu[x]<<" "<<duu[prvi]<<" "<<ras<<" "<<ds[t]<<endl;
long long resss=manji(ds[prvi]+dt[y],dt[prvi]+ds[y]);
if(resss+duu[x]-duu[prvi]+ras!=ds[t])continue;
//if(x==2 && ty==0 && y==1 && tt==1)cout<<"qrac2"<<endl;
ras=0;
}
if(du[y][tt]>du[x][ty]+ras)
{
du[y][tt]=du[x][ty]+ras;
pq2.push({-du[y][tt],{y,tt}});
if(tt==1)first[y]=prvi;
}
}
}
}
//for(int i=1;i<=n;i++)cout<<i<<" "<<du[i][0]<<" "<<du[i][1]<<" "<<du[i][2]<<endl;
long long sol=du[v][0];
if(sol>du[v][1])sol=du[v][1];
if(sol>du[v][2])sol=du[v][2];
cout<<sol<<endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
490 ms |
22880 KB |
Output is correct |
2 |
Correct |
496 ms |
24608 KB |
Output is correct |
3 |
Correct |
631 ms |
30580 KB |
Output is correct |
4 |
Correct |
423 ms |
31980 KB |
Output is correct |
5 |
Correct |
555 ms |
37348 KB |
Output is correct |
6 |
Correct |
510 ms |
41316 KB |
Output is correct |
7 |
Correct |
567 ms |
45020 KB |
Output is correct |
8 |
Correct |
598 ms |
48456 KB |
Output is correct |
9 |
Correct |
482 ms |
48456 KB |
Output is correct |
10 |
Correct |
351 ms |
48456 KB |
Output is correct |
11 |
Correct |
159 ms |
48456 KB |
Output is correct |
12 |
Correct |
469 ms |
48456 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
538 ms |
50748 KB |
Output is correct |
2 |
Correct |
543 ms |
53320 KB |
Output is correct |
3 |
Correct |
535 ms |
55420 KB |
Output is correct |
4 |
Correct |
495 ms |
55420 KB |
Output is correct |
5 |
Correct |
519 ms |
55420 KB |
Output is correct |
6 |
Correct |
521 ms |
57340 KB |
Output is correct |
7 |
Correct |
601 ms |
62644 KB |
Output is correct |
8 |
Correct |
536 ms |
64156 KB |
Output is correct |
9 |
Correct |
560 ms |
67556 KB |
Output is correct |
10 |
Correct |
529 ms |
71000 KB |
Output is correct |
11 |
Correct |
178 ms |
71000 KB |
Output is correct |
12 |
Correct |
491 ms |
74344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
74344 KB |
Output is correct |
2 |
Correct |
4 ms |
74344 KB |
Output is correct |
3 |
Correct |
4 ms |
74344 KB |
Output is correct |
4 |
Correct |
21 ms |
74344 KB |
Output is correct |
5 |
Correct |
14 ms |
74344 KB |
Output is correct |
6 |
Correct |
5 ms |
74344 KB |
Output is correct |
7 |
Correct |
6 ms |
74344 KB |
Output is correct |
8 |
Correct |
6 ms |
74344 KB |
Output is correct |
9 |
Correct |
5 ms |
74344 KB |
Output is correct |
10 |
Correct |
15 ms |
74344 KB |
Output is correct |
11 |
Correct |
4 ms |
74344 KB |
Output is correct |
12 |
Correct |
4 ms |
74344 KB |
Output is correct |
13 |
Correct |
4 ms |
74344 KB |
Output is correct |
14 |
Correct |
5 ms |
74344 KB |
Output is correct |
15 |
Correct |
5 ms |
74344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
490 ms |
22880 KB |
Output is correct |
2 |
Correct |
496 ms |
24608 KB |
Output is correct |
3 |
Correct |
631 ms |
30580 KB |
Output is correct |
4 |
Correct |
423 ms |
31980 KB |
Output is correct |
5 |
Correct |
555 ms |
37348 KB |
Output is correct |
6 |
Correct |
510 ms |
41316 KB |
Output is correct |
7 |
Correct |
567 ms |
45020 KB |
Output is correct |
8 |
Correct |
598 ms |
48456 KB |
Output is correct |
9 |
Correct |
482 ms |
48456 KB |
Output is correct |
10 |
Correct |
351 ms |
48456 KB |
Output is correct |
11 |
Correct |
159 ms |
48456 KB |
Output is correct |
12 |
Correct |
469 ms |
48456 KB |
Output is correct |
13 |
Correct |
538 ms |
50748 KB |
Output is correct |
14 |
Correct |
543 ms |
53320 KB |
Output is correct |
15 |
Correct |
535 ms |
55420 KB |
Output is correct |
16 |
Correct |
495 ms |
55420 KB |
Output is correct |
17 |
Correct |
519 ms |
55420 KB |
Output is correct |
18 |
Correct |
521 ms |
57340 KB |
Output is correct |
19 |
Correct |
601 ms |
62644 KB |
Output is correct |
20 |
Correct |
536 ms |
64156 KB |
Output is correct |
21 |
Correct |
560 ms |
67556 KB |
Output is correct |
22 |
Correct |
529 ms |
71000 KB |
Output is correct |
23 |
Correct |
178 ms |
71000 KB |
Output is correct |
24 |
Correct |
491 ms |
74344 KB |
Output is correct |
25 |
Correct |
15 ms |
74344 KB |
Output is correct |
26 |
Correct |
4 ms |
74344 KB |
Output is correct |
27 |
Correct |
4 ms |
74344 KB |
Output is correct |
28 |
Correct |
21 ms |
74344 KB |
Output is correct |
29 |
Correct |
14 ms |
74344 KB |
Output is correct |
30 |
Correct |
5 ms |
74344 KB |
Output is correct |
31 |
Correct |
6 ms |
74344 KB |
Output is correct |
32 |
Correct |
6 ms |
74344 KB |
Output is correct |
33 |
Correct |
5 ms |
74344 KB |
Output is correct |
34 |
Correct |
15 ms |
74344 KB |
Output is correct |
35 |
Correct |
4 ms |
74344 KB |
Output is correct |
36 |
Correct |
4 ms |
74344 KB |
Output is correct |
37 |
Correct |
4 ms |
74344 KB |
Output is correct |
38 |
Correct |
5 ms |
74344 KB |
Output is correct |
39 |
Correct |
5 ms |
74344 KB |
Output is correct |
40 |
Correct |
386 ms |
78008 KB |
Output is correct |
41 |
Correct |
405 ms |
78008 KB |
Output is correct |
42 |
Correct |
397 ms |
78008 KB |
Output is correct |
43 |
Correct |
210 ms |
78008 KB |
Output is correct |
44 |
Correct |
188 ms |
78008 KB |
Output is correct |
45 |
Correct |
483 ms |
83412 KB |
Output is correct |
46 |
Correct |
474 ms |
86520 KB |
Output is correct |
47 |
Correct |
436 ms |
89532 KB |
Output is correct |
48 |
Correct |
231 ms |
89532 KB |
Output is correct |
49 |
Correct |
337 ms |
95988 KB |
Output is correct |
50 |
Correct |
486 ms |
96432 KB |
Output is correct |
51 |
Correct |
468 ms |
96432 KB |
Output is correct |