#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll n,m,S,T,U,V,ta,tb,tc,i,j,has;
ll jar[4][101010];
vector<ll> v[101010];
vector<ll> w[101010];
vector<ll> vi[101010];
ll d[101010][2];
ll depe(ll aa,ll bb)
{
if(d[aa][bb]==-1)
{
if(bb==0)
d[aa][bb]=jar[2][aa];
else
d[aa][bb]=jar[3][aa];
ll ii;
for(ii=0;ii<vi[aa].size();ii++)
d[aa][bb]=min(d[aa][bb],depe(vi[aa][ii],bb));
}
return d[aa][bb];
}
void buat(ll aa,ll bb)
{
priority_queue<pair<ll,ll> > pq;
jar[bb][aa]=0;
pq.push(mp(0,aa));
while(!pq.empty())
{
ll dis=-pq.top().fi;
ll u=pq.top().se;
pq.pop();
if(dis>jar[bb][u])continue;
ll ii;
for(ii=0;ii<v[u].size();ii++)
if((jar[bb][v[u][ii]]==-1)||(jar[bb][v[u][ii]]>(dis+w[u][ii])))
{
jar[bb][v[u][ii]]=dis+w[u][ii];
pq.push(mp(-jar[bb][v[u][ii]],v[u][ii]));
}
}
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m;
cin>>S>>T;
cin>>U>>V;
for(i=1;i<=m;i++)
{
cin>>ta>>tb>>tc;
v[ta].pb(tb);
w[ta].pb(tc);
v[tb].pb(ta);
w[tb].pb(tc);
}
memset(jar,-1,sizeof(jar));
buat(S,0);
buat(T,1);
buat(U,2);
buat(V,3);
for(i=1;i<=n;i++)
for(j=0;j<v[i].size();j++)
{
//cout<<i<<" "<<v[i][j]<<" "<<jar[0][i]<<" "<<w[i][j]<<" "<<jar[1][v[i][j]]<<" "<<jar[0][T]<<"\n";
if(jar[0][i]+w[i][j]+jar[1][v[i][j]]==jar[0][T])
{
//cout<<v[i][j]<<" "<<i<<"\n";
vi[v[i][j]].pb(i);
}
}
has=jar[2][V];
memset(d,-1,sizeof(d));
for(i=1;i<=n;i++)
{
has=min(has,depe(i,0)+jar[3][i]);
has=min(has,depe(i,1)+jar[2][i]);
}
cout<<has<<"\n";
}
Compilation message
commuter_pass.cpp: In function 'll depe(ll, ll)':
commuter_pass.cpp:23:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ii=0;ii<vi[aa].size();ii++)
~~^~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void buat(ll, ll)':
commuter_pass.cpp:40:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ii=0;ii<v[u].size();ii++)
~~^~~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:68: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 |
534 ms |
26468 KB |
Output is correct |
2 |
Correct |
554 ms |
25284 KB |
Output is correct |
3 |
Correct |
546 ms |
28320 KB |
Output is correct |
4 |
Correct |
486 ms |
26336 KB |
Output is correct |
5 |
Correct |
507 ms |
25644 KB |
Output is correct |
6 |
Correct |
502 ms |
26636 KB |
Output is correct |
7 |
Correct |
523 ms |
25964 KB |
Output is correct |
8 |
Correct |
527 ms |
25620 KB |
Output is correct |
9 |
Correct |
486 ms |
25068 KB |
Output is correct |
10 |
Correct |
456 ms |
25008 KB |
Output is correct |
11 |
Correct |
263 ms |
20636 KB |
Output is correct |
12 |
Correct |
515 ms |
25124 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
606 ms |
26276 KB |
Output is correct |
2 |
Correct |
576 ms |
26160 KB |
Output is correct |
3 |
Correct |
594 ms |
25816 KB |
Output is correct |
4 |
Correct |
598 ms |
26468 KB |
Output is correct |
5 |
Correct |
594 ms |
29520 KB |
Output is correct |
6 |
Correct |
588 ms |
31356 KB |
Output is correct |
7 |
Correct |
613 ms |
30208 KB |
Output is correct |
8 |
Correct |
578 ms |
29220 KB |
Output is correct |
9 |
Correct |
597 ms |
29732 KB |
Output is correct |
10 |
Correct |
590 ms |
28936 KB |
Output is correct |
11 |
Correct |
326 ms |
25084 KB |
Output is correct |
12 |
Correct |
682 ms |
31344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
13688 KB |
Output is correct |
2 |
Correct |
12 ms |
12288 KB |
Output is correct |
3 |
Correct |
12 ms |
12288 KB |
Output is correct |
4 |
Correct |
30 ms |
15500 KB |
Output is correct |
5 |
Correct |
21 ms |
13952 KB |
Output is correct |
6 |
Correct |
13 ms |
12288 KB |
Output is correct |
7 |
Correct |
13 ms |
12416 KB |
Output is correct |
8 |
Correct |
14 ms |
12468 KB |
Output is correct |
9 |
Correct |
13 ms |
12416 KB |
Output is correct |
10 |
Correct |
20 ms |
13952 KB |
Output is correct |
11 |
Correct |
12 ms |
12288 KB |
Output is correct |
12 |
Correct |
12 ms |
12288 KB |
Output is correct |
13 |
Correct |
12 ms |
12288 KB |
Output is correct |
14 |
Correct |
13 ms |
12288 KB |
Output is correct |
15 |
Correct |
13 ms |
12288 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
534 ms |
26468 KB |
Output is correct |
2 |
Correct |
554 ms |
25284 KB |
Output is correct |
3 |
Correct |
546 ms |
28320 KB |
Output is correct |
4 |
Correct |
486 ms |
26336 KB |
Output is correct |
5 |
Correct |
507 ms |
25644 KB |
Output is correct |
6 |
Correct |
502 ms |
26636 KB |
Output is correct |
7 |
Correct |
523 ms |
25964 KB |
Output is correct |
8 |
Correct |
527 ms |
25620 KB |
Output is correct |
9 |
Correct |
486 ms |
25068 KB |
Output is correct |
10 |
Correct |
456 ms |
25008 KB |
Output is correct |
11 |
Correct |
263 ms |
20636 KB |
Output is correct |
12 |
Correct |
515 ms |
25124 KB |
Output is correct |
13 |
Correct |
606 ms |
26276 KB |
Output is correct |
14 |
Correct |
576 ms |
26160 KB |
Output is correct |
15 |
Correct |
594 ms |
25816 KB |
Output is correct |
16 |
Correct |
598 ms |
26468 KB |
Output is correct |
17 |
Correct |
594 ms |
29520 KB |
Output is correct |
18 |
Correct |
588 ms |
31356 KB |
Output is correct |
19 |
Correct |
613 ms |
30208 KB |
Output is correct |
20 |
Correct |
578 ms |
29220 KB |
Output is correct |
21 |
Correct |
597 ms |
29732 KB |
Output is correct |
22 |
Correct |
590 ms |
28936 KB |
Output is correct |
23 |
Correct |
326 ms |
25084 KB |
Output is correct |
24 |
Correct |
682 ms |
31344 KB |
Output is correct |
25 |
Correct |
21 ms |
13688 KB |
Output is correct |
26 |
Correct |
12 ms |
12288 KB |
Output is correct |
27 |
Correct |
12 ms |
12288 KB |
Output is correct |
28 |
Correct |
30 ms |
15500 KB |
Output is correct |
29 |
Correct |
21 ms |
13952 KB |
Output is correct |
30 |
Correct |
13 ms |
12288 KB |
Output is correct |
31 |
Correct |
13 ms |
12416 KB |
Output is correct |
32 |
Correct |
14 ms |
12468 KB |
Output is correct |
33 |
Correct |
13 ms |
12416 KB |
Output is correct |
34 |
Correct |
20 ms |
13952 KB |
Output is correct |
35 |
Correct |
12 ms |
12288 KB |
Output is correct |
36 |
Correct |
12 ms |
12288 KB |
Output is correct |
37 |
Correct |
12 ms |
12288 KB |
Output is correct |
38 |
Correct |
13 ms |
12288 KB |
Output is correct |
39 |
Correct |
13 ms |
12288 KB |
Output is correct |
40 |
Correct |
465 ms |
29544 KB |
Output is correct |
41 |
Correct |
582 ms |
28348 KB |
Output is correct |
42 |
Correct |
523 ms |
28664 KB |
Output is correct |
43 |
Correct |
345 ms |
25336 KB |
Output is correct |
44 |
Correct |
359 ms |
25960 KB |
Output is correct |
45 |
Correct |
613 ms |
31044 KB |
Output is correct |
46 |
Correct |
593 ms |
30772 KB |
Output is correct |
47 |
Correct |
509 ms |
29720 KB |
Output is correct |
48 |
Correct |
359 ms |
24092 KB |
Output is correct |
49 |
Correct |
452 ms |
29324 KB |
Output is correct |
50 |
Correct |
590 ms |
30352 KB |
Output is correct |
51 |
Correct |
643 ms |
31100 KB |
Output is correct |