#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define fr first
#define sc second
long long n,m,st[2],fn[2],wg[200069],nr[2][100069],inf=1e18;
pair<long long,long long> ed[200069];
vector<pair<long long,long long>> al[100069];
priority_queue<pair<long long,pair<bool,long long>>> pq;
vector<long long> cd[2][100069];
bitset<100069> vtd[2];
void dfs(long long xx,long long x,long long w)
{
long long i,sz=cd[xx][x].size(),l;
vtd[xx][x]=1;
if(w<nr[1][x])
{
pq.push({-w,{1,x}});
nr[1][x]=w;
}
for(i=0;i<sz;i++)
{
l=cd[xx][x][i];
if(!vtd[xx][l])
{
dfs(xx,l,w);
}
}
}
int main()
{
long long i,ii,k,l,w,sz,ww,e;
scanf("%lld%lld",&n,&m);
for(ii=0;ii<2;ii++)
{
scanf("%lld%lld",st+ii,fn+ii);
}
for(i=1;i<=m;i++)
{
scanf("%lld%lld%lld",&k,&l,&w);
ed[i]={k,l};
wg[i]=w;
al[k].push_back({l,w});
al[l].push_back({k,w});
}
for(ii=0;ii<2;ii++)
{
for(i=1;i<=n;i++)
{
nr[ii][i]=inf;
}
pq.push({0,{ii,st[0]}});
nr[ii][st[0]]=0;
swap(st[0],fn[0]);
}
for(;!pq.empty();)
{
e=pq.top().sc.fr;
k=pq.top().sc.sc;
w=-pq.top().fr;
pq.pop();
if(w>nr[e][k])
{
continue;
}
sz=al[k].size();
for(i=0;i<sz;i++)
{
l=al[k][i].fr;
ww=al[k][i].sc;
if(w+ww<nr[e][l])
{
pq.push({-w-ww,{e,l}});
nr[e][l]=w+ww;
}
}
}
for(i=1;i<=m;i++)
{
k=ed[i].fr;
l=ed[i].sc;
if(nr[0][k]>nr[0][l])
{
swap(k,l);
}
if(nr[0][k]+wg[i]+nr[1][l]==nr[0][fn[0]])
{
cd[0][k].push_back(l);
cd[1][l].push_back(k);
}
}
for(ii=0;ii<2;ii++)
{
for(i=1;i<=n;i++)
{
nr[ii][i]=inf;
}
}
pq.push({0,{0,st[1]}});
nr[0][st[1]]=0;
for(;!pq.empty();)
{
e=pq.top().sc.fr;
k=pq.top().sc.sc;
w=-pq.top().fr;
pq.pop();
if(w>nr[e][k])
{
continue;
}
if(!e)
{
for(ii=0;ii<2;ii++)
{
if(!vtd[ii][k])
{
dfs(ii,k,w);
}
}
}
sz=al[k].size();
for(i=0;i<sz;i++)
{
l=al[k][i].fr;
ww=al[k][i].sc;
if(w+ww<nr[e][l])
{
pq.push({-w-ww,{e,l}});
nr[e][l]=w+ww;
}
}
}
printf("%lld\n",nr[1][fn[1]]);
}
Compilation message
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
40 | scanf("%lld%lld",&n,&m);
| ~~~~~^~~~~~~~~~~~~~~~~~
commuter_pass.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
43 | scanf("%lld%lld",st+ii,fn+ii);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:47:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
47 | scanf("%lld%lld%lld",&k,&l,&w);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
451 ms |
34124 KB |
Output is correct |
2 |
Correct |
489 ms |
31456 KB |
Output is correct |
3 |
Correct |
499 ms |
43620 KB |
Output is correct |
4 |
Correct |
436 ms |
31080 KB |
Output is correct |
5 |
Correct |
479 ms |
32356 KB |
Output is correct |
6 |
Correct |
466 ms |
34272 KB |
Output is correct |
7 |
Correct |
472 ms |
33508 KB |
Output is correct |
8 |
Correct |
535 ms |
33256 KB |
Output is correct |
9 |
Correct |
495 ms |
31724 KB |
Output is correct |
10 |
Correct |
419 ms |
31720 KB |
Output is correct |
11 |
Correct |
254 ms |
28588 KB |
Output is correct |
12 |
Correct |
528 ms |
31464 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
572 ms |
34856 KB |
Output is correct |
2 |
Correct |
580 ms |
34916 KB |
Output is correct |
3 |
Correct |
597 ms |
35556 KB |
Output is correct |
4 |
Correct |
563 ms |
34144 KB |
Output is correct |
5 |
Correct |
559 ms |
34772 KB |
Output is correct |
6 |
Correct |
587 ms |
42216 KB |
Output is correct |
7 |
Correct |
585 ms |
44976 KB |
Output is correct |
8 |
Correct |
545 ms |
34676 KB |
Output is correct |
9 |
Correct |
538 ms |
36320 KB |
Output is correct |
10 |
Correct |
549 ms |
33892 KB |
Output is correct |
11 |
Correct |
276 ms |
33644 KB |
Output is correct |
12 |
Correct |
544 ms |
43128 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
9856 KB |
Output is correct |
2 |
Correct |
6 ms |
7424 KB |
Output is correct |
3 |
Correct |
6 ms |
7456 KB |
Output is correct |
4 |
Correct |
27 ms |
11776 KB |
Output is correct |
5 |
Correct |
16 ms |
9600 KB |
Output is correct |
6 |
Correct |
7 ms |
7552 KB |
Output is correct |
7 |
Correct |
9 ms |
7680 KB |
Output is correct |
8 |
Correct |
7 ms |
7808 KB |
Output is correct |
9 |
Correct |
6 ms |
7552 KB |
Output is correct |
10 |
Correct |
19 ms |
9600 KB |
Output is correct |
11 |
Correct |
6 ms |
7424 KB |
Output is correct |
12 |
Correct |
5 ms |
7424 KB |
Output is correct |
13 |
Correct |
6 ms |
7424 KB |
Output is correct |
14 |
Correct |
6 ms |
7552 KB |
Output is correct |
15 |
Correct |
6 ms |
7552 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
451 ms |
34124 KB |
Output is correct |
2 |
Correct |
489 ms |
31456 KB |
Output is correct |
3 |
Correct |
499 ms |
43620 KB |
Output is correct |
4 |
Correct |
436 ms |
31080 KB |
Output is correct |
5 |
Correct |
479 ms |
32356 KB |
Output is correct |
6 |
Correct |
466 ms |
34272 KB |
Output is correct |
7 |
Correct |
472 ms |
33508 KB |
Output is correct |
8 |
Correct |
535 ms |
33256 KB |
Output is correct |
9 |
Correct |
495 ms |
31724 KB |
Output is correct |
10 |
Correct |
419 ms |
31720 KB |
Output is correct |
11 |
Correct |
254 ms |
28588 KB |
Output is correct |
12 |
Correct |
528 ms |
31464 KB |
Output is correct |
13 |
Correct |
572 ms |
34856 KB |
Output is correct |
14 |
Correct |
580 ms |
34916 KB |
Output is correct |
15 |
Correct |
597 ms |
35556 KB |
Output is correct |
16 |
Correct |
563 ms |
34144 KB |
Output is correct |
17 |
Correct |
559 ms |
34772 KB |
Output is correct |
18 |
Correct |
587 ms |
42216 KB |
Output is correct |
19 |
Correct |
585 ms |
44976 KB |
Output is correct |
20 |
Correct |
545 ms |
34676 KB |
Output is correct |
21 |
Correct |
538 ms |
36320 KB |
Output is correct |
22 |
Correct |
549 ms |
33892 KB |
Output is correct |
23 |
Correct |
276 ms |
33644 KB |
Output is correct |
24 |
Correct |
544 ms |
43128 KB |
Output is correct |
25 |
Correct |
18 ms |
9856 KB |
Output is correct |
26 |
Correct |
6 ms |
7424 KB |
Output is correct |
27 |
Correct |
6 ms |
7456 KB |
Output is correct |
28 |
Correct |
27 ms |
11776 KB |
Output is correct |
29 |
Correct |
16 ms |
9600 KB |
Output is correct |
30 |
Correct |
7 ms |
7552 KB |
Output is correct |
31 |
Correct |
9 ms |
7680 KB |
Output is correct |
32 |
Correct |
7 ms |
7808 KB |
Output is correct |
33 |
Correct |
6 ms |
7552 KB |
Output is correct |
34 |
Correct |
19 ms |
9600 KB |
Output is correct |
35 |
Correct |
6 ms |
7424 KB |
Output is correct |
36 |
Correct |
5 ms |
7424 KB |
Output is correct |
37 |
Correct |
6 ms |
7424 KB |
Output is correct |
38 |
Correct |
6 ms |
7552 KB |
Output is correct |
39 |
Correct |
6 ms |
7552 KB |
Output is correct |
40 |
Correct |
447 ms |
35036 KB |
Output is correct |
41 |
Correct |
475 ms |
31464 KB |
Output is correct |
42 |
Correct |
452 ms |
31540 KB |
Output is correct |
43 |
Correct |
275 ms |
33768 KB |
Output is correct |
44 |
Correct |
273 ms |
33768 KB |
Output is correct |
45 |
Correct |
516 ms |
35916 KB |
Output is correct |
46 |
Correct |
505 ms |
35688 KB |
Output is correct |
47 |
Correct |
449 ms |
31076 KB |
Output is correct |
48 |
Correct |
281 ms |
28140 KB |
Output is correct |
49 |
Correct |
389 ms |
34652 KB |
Output is correct |
50 |
Correct |
492 ms |
34400 KB |
Output is correct |
51 |
Correct |
512 ms |
36576 KB |
Output is correct |