#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll n,m,S,T,U,V,i,dis[101010][6],ta,tb,tc,b[101010][6],j,d[101010][2],has;
vector<ll> v[101010],w[101010],x[101010];
void djik(ll aa,ll bb)
{
priority_queue<pair<ll,pair<ll,ll> > > pq;
ll ii;
for(ii=1;ii<=n;ii++)dis[ii][bb]=1e18;
dis[aa][bb]=0;
pq.push(mp(0,mp(aa,-1)));
while(!pq.empty())
{
ll jar=-pq.top().fi;
ll u=pq.top().se.fi;
ll par=pq.top().se.se;
pq.pop();
if(b[u][bb])continue;
b[u][bb]=1;
for(ii=0;ii<v[u].size();ii++)
{
ll nx=v[u][ii];
if(dis[nx][bb]>=(jar+w[u][ii]))
{
dis[nx][bb]=jar+w[u][ii];
pq.push(mp(-jar-w[u][ii],mp(nx,u)));
}
}
}
}
ll depe(ll aa,ll bb)
{
if(d[aa][bb]==-1)
{
if(bb==0)
d[aa][bb]=dis[aa][2];
else
d[aa][bb]=dis[aa][3];
ll ii;
for(ii=0;ii<x[aa].size();ii++)
d[aa][bb]=min(d[aa][bb],depe(x[aa][ii],bb));
}
return d[aa][bb];
}
int main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
cin>>n>>m;
cin>>S>>T;
cin>>U>>V;
for(i=1;i<=m;i++)
{
cin>>ta>>tb>>tc;
v[ta].pb(tb);
v[tb].pb(ta);
w[ta].pb(tc);
w[tb].pb(tc);
}
djik(S,0);
djik(T,1);
djik(U,2);
djik(V,3);
for(i=1;i<=n;i++)
{
for(j=0;j<v[i].size();j++)
{
if((dis[i][0]+w[i][j]+dis[v[i][j]][1])==dis[T][0])
{
// cout<<i<<" "<<v[i][j]<<"\n";
x[v[i][j]].pb(i);
}
}
}
has=1e18;
memset(d,-1,sizeof(d));
for(i=1;i<=n;i++)
{
//cout<<i<<" "<<depe(i,0)<<" "<<depe(i,1)<<"\n";
has=min(has,depe(i,0)+dis[i][3]);
has=min(has,depe(i,1)+dis[i][2]);
}
cout<<has<<"\n";
//for(i=1;i<=n;i++)cout<<i<<" S="<<dis[i][2]<<" T="<<dis[i][3]<<"\n";
}
Compilation message
commuter_pass.cpp: In function 'void djik(long long int, long long int)':
commuter_pass.cpp:25:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ii=0;ii<v[u].size();ii++)
~~^~~~~~~~~~~~
commuter_pass.cpp:21:6: warning: unused variable 'par' [-Wunused-variable]
ll par=pq.top().se.se;
^~~
commuter_pass.cpp: In function 'long long int depe(long long int, long long int)':
commuter_pass.cpp:45:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ii=0;ii<x[aa].size();ii++)
~~^~~~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:70:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<v[i].size();j++)
~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
653 ms |
37976 KB |
Output is correct |
2 |
Correct |
676 ms |
35740 KB |
Output is correct |
3 |
Correct |
685 ms |
38960 KB |
Output is correct |
4 |
Correct |
638 ms |
38136 KB |
Output is correct |
5 |
Correct |
595 ms |
35404 KB |
Output is correct |
6 |
Correct |
623 ms |
38180 KB |
Output is correct |
7 |
Correct |
656 ms |
35764 KB |
Output is correct |
8 |
Correct |
565 ms |
35712 KB |
Output is correct |
9 |
Correct |
522 ms |
36476 KB |
Output is correct |
10 |
Correct |
502 ms |
36968 KB |
Output is correct |
11 |
Correct |
270 ms |
28920 KB |
Output is correct |
12 |
Correct |
540 ms |
36312 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
562 ms |
36088 KB |
Output is correct |
2 |
Correct |
577 ms |
35652 KB |
Output is correct |
3 |
Correct |
666 ms |
35712 KB |
Output is correct |
4 |
Correct |
649 ms |
36252 KB |
Output is correct |
5 |
Correct |
715 ms |
35920 KB |
Output is correct |
6 |
Correct |
630 ms |
37844 KB |
Output is correct |
7 |
Correct |
764 ms |
36520 KB |
Output is correct |
8 |
Correct |
682 ms |
35560 KB |
Output is correct |
9 |
Correct |
699 ms |
35920 KB |
Output is correct |
10 |
Correct |
706 ms |
35556 KB |
Output is correct |
11 |
Correct |
294 ms |
31336 KB |
Output is correct |
12 |
Correct |
561 ms |
37864 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
35 ms |
10840 KB |
Output is correct |
2 |
Correct |
8 ms |
9208 KB |
Output is correct |
3 |
Correct |
8 ms |
9208 KB |
Output is correct |
4 |
Correct |
61 ms |
12536 KB |
Output is correct |
5 |
Correct |
18 ms |
10872 KB |
Output is correct |
6 |
Correct |
10 ms |
9208 KB |
Output is correct |
7 |
Correct |
12 ms |
9336 KB |
Output is correct |
8 |
Correct |
11 ms |
9336 KB |
Output is correct |
9 |
Correct |
10 ms |
9208 KB |
Output is correct |
10 |
Correct |
23 ms |
10920 KB |
Output is correct |
11 |
Correct |
9 ms |
9080 KB |
Output is correct |
12 |
Correct |
12 ms |
9080 KB |
Output is correct |
13 |
Correct |
10 ms |
9080 KB |
Output is correct |
14 |
Correct |
9 ms |
9212 KB |
Output is correct |
15 |
Correct |
13 ms |
9208 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
653 ms |
37976 KB |
Output is correct |
2 |
Correct |
676 ms |
35740 KB |
Output is correct |
3 |
Correct |
685 ms |
38960 KB |
Output is correct |
4 |
Correct |
638 ms |
38136 KB |
Output is correct |
5 |
Correct |
595 ms |
35404 KB |
Output is correct |
6 |
Correct |
623 ms |
38180 KB |
Output is correct |
7 |
Correct |
656 ms |
35764 KB |
Output is correct |
8 |
Correct |
565 ms |
35712 KB |
Output is correct |
9 |
Correct |
522 ms |
36476 KB |
Output is correct |
10 |
Correct |
502 ms |
36968 KB |
Output is correct |
11 |
Correct |
270 ms |
28920 KB |
Output is correct |
12 |
Correct |
540 ms |
36312 KB |
Output is correct |
13 |
Correct |
562 ms |
36088 KB |
Output is correct |
14 |
Correct |
577 ms |
35652 KB |
Output is correct |
15 |
Correct |
666 ms |
35712 KB |
Output is correct |
16 |
Correct |
649 ms |
36252 KB |
Output is correct |
17 |
Correct |
715 ms |
35920 KB |
Output is correct |
18 |
Correct |
630 ms |
37844 KB |
Output is correct |
19 |
Correct |
764 ms |
36520 KB |
Output is correct |
20 |
Correct |
682 ms |
35560 KB |
Output is correct |
21 |
Correct |
699 ms |
35920 KB |
Output is correct |
22 |
Correct |
706 ms |
35556 KB |
Output is correct |
23 |
Correct |
294 ms |
31336 KB |
Output is correct |
24 |
Correct |
561 ms |
37864 KB |
Output is correct |
25 |
Correct |
35 ms |
10840 KB |
Output is correct |
26 |
Correct |
8 ms |
9208 KB |
Output is correct |
27 |
Correct |
8 ms |
9208 KB |
Output is correct |
28 |
Correct |
61 ms |
12536 KB |
Output is correct |
29 |
Correct |
18 ms |
10872 KB |
Output is correct |
30 |
Correct |
10 ms |
9208 KB |
Output is correct |
31 |
Correct |
12 ms |
9336 KB |
Output is correct |
32 |
Correct |
11 ms |
9336 KB |
Output is correct |
33 |
Correct |
10 ms |
9208 KB |
Output is correct |
34 |
Correct |
23 ms |
10920 KB |
Output is correct |
35 |
Correct |
9 ms |
9080 KB |
Output is correct |
36 |
Correct |
12 ms |
9080 KB |
Output is correct |
37 |
Correct |
10 ms |
9080 KB |
Output is correct |
38 |
Correct |
9 ms |
9212 KB |
Output is correct |
39 |
Correct |
13 ms |
9208 KB |
Output is correct |
40 |
Correct |
585 ms |
38132 KB |
Output is correct |
41 |
Correct |
648 ms |
36532 KB |
Output is correct |
42 |
Correct |
575 ms |
36324 KB |
Output is correct |
43 |
Correct |
330 ms |
31800 KB |
Output is correct |
44 |
Correct |
365 ms |
32248 KB |
Output is correct |
45 |
Correct |
727 ms |
37276 KB |
Output is correct |
46 |
Correct |
679 ms |
36984 KB |
Output is correct |
47 |
Correct |
565 ms |
37956 KB |
Output is correct |
48 |
Correct |
306 ms |
30072 KB |
Output is correct |
49 |
Correct |
598 ms |
38120 KB |
Output is correct |
50 |
Correct |
660 ms |
36332 KB |
Output is correct |
51 |
Correct |
667 ms |
37212 KB |
Output is correct |