#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define MAXN 100005
typedef long long ll;
using namespace std;
ll n,m,a,b,x,y;
vector<pair<ll,ll> > niz[MAXN];
vector<ll > preci[MAXN];
set<pair<ll,ll> > q;
ll oda[MAXN],odb[MAXN],odx[MAXN],ody[MAXN],dece[MAXN];
vector<ll> nzm;
ll dpx[MAXN],dpy[MAXN];
ll res;
void dijkstra(ll s,ll *gde){
q.clear();
q.insert(mp(0,s));
while(!q.empty()){
ll tu=q.begin()->first;
ll t=q.begin()->second;
q.erase(q.begin());
if(gde[t] && t!=s){
continue;
}
gde[t]=tu;
for(auto x:niz[t]){
if(!gde[x.first] && x.first!=s){
q.insert(mp(tu+x.second,x.first));
}
}
}
}
int main()///SVE U LONG LONG
{
scanf("%lld %lld", &n, &m);
scanf("%lld %lld", &a, &b);
scanf("%lld %lld", &x, &y);
for(ll i=1;i<=m;i++){
ll t1,t2,t3;
scanf("%lld %lld %lld", &t1, &t2, &t3);
niz[t1].pb(mp(t2,t3));
niz[t2].pb(mp(t1,t3));
}
dijkstra(a,oda);
dijkstra(b,odb);
dijkstra(x,odx);
dijkstra(y,ody);
res=odx[y];
for(ll i=1;i<=n;i++){
if(!(oda[i]+odb[i]== oda[b]))continue;
dpx[i]=odx[i];
dpy[i]=ody[i];
for(auto x:niz[i]){
if(x.second+odb[x.first]+oda[i]==oda[b]){
dece[i]++;
preci[x.first].pb(i);
}
}
if(!dece[i])nzm.pb(i);//samo b lol
}
while(!nzm.empty()){
ll t=nzm.back();
nzm.pop_back();
res = min(res,min(dpx[t]+ody[t],dpy[t]+odx[t]));
//printf(" %d %d %d %d %d\n",t,dpx[t],odx[t],dpy[t],ody[t]);
for(auto x:preci[t]){
dece[x]--;
if(!dece[x])nzm.pb(x);
dpx[x]=min(dpx[x],dpx[t]);
dpy[x]=min(dpy[x],dpy[t]);
}
}
printf("%lld",res);
return 0;
}
Compilation message
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld", &n, &m);
~~~~~^~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld", &a, &b);
~~~~~^~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld", &x, &y);
~~~~~^~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld %lld", &t1, &t2, &t3);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
873 ms |
29136 KB |
Output is correct |
2 |
Correct |
676 ms |
29740 KB |
Output is correct |
3 |
Correct |
712 ms |
30116 KB |
Output is correct |
4 |
Correct |
813 ms |
28408 KB |
Output is correct |
5 |
Correct |
648 ms |
28408 KB |
Output is correct |
6 |
Correct |
933 ms |
29684 KB |
Output is correct |
7 |
Correct |
653 ms |
29404 KB |
Output is correct |
8 |
Correct |
677 ms |
29460 KB |
Output is correct |
9 |
Correct |
715 ms |
27968 KB |
Output is correct |
10 |
Correct |
652 ms |
27384 KB |
Output is correct |
11 |
Correct |
228 ms |
18808 KB |
Output is correct |
12 |
Correct |
622 ms |
28256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
842 ms |
30328 KB |
Output is correct |
2 |
Correct |
662 ms |
28792 KB |
Output is correct |
3 |
Correct |
690 ms |
28664 KB |
Output is correct |
4 |
Correct |
650 ms |
28864 KB |
Output is correct |
5 |
Correct |
672 ms |
28792 KB |
Output is correct |
6 |
Correct |
692 ms |
29820 KB |
Output is correct |
7 |
Correct |
682 ms |
28824 KB |
Output is correct |
8 |
Correct |
684 ms |
28772 KB |
Output is correct |
9 |
Correct |
726 ms |
28792 KB |
Output is correct |
10 |
Correct |
660 ms |
28892 KB |
Output is correct |
11 |
Correct |
231 ms |
19576 KB |
Output is correct |
12 |
Correct |
672 ms |
29916 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
33 ms |
7160 KB |
Output is correct |
2 |
Correct |
7 ms |
5112 KB |
Output is correct |
3 |
Correct |
7 ms |
5112 KB |
Output is correct |
4 |
Correct |
58 ms |
9196 KB |
Output is correct |
5 |
Correct |
35 ms |
7544 KB |
Output is correct |
6 |
Correct |
8 ms |
5240 KB |
Output is correct |
7 |
Correct |
9 ms |
5368 KB |
Output is correct |
8 |
Correct |
11 ms |
5368 KB |
Output is correct |
9 |
Correct |
8 ms |
5240 KB |
Output is correct |
10 |
Correct |
39 ms |
7544 KB |
Output is correct |
11 |
Correct |
8 ms |
5112 KB |
Output is correct |
12 |
Correct |
7 ms |
5108 KB |
Output is correct |
13 |
Correct |
7 ms |
5112 KB |
Output is correct |
14 |
Correct |
8 ms |
5280 KB |
Output is correct |
15 |
Correct |
7 ms |
5116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
873 ms |
29136 KB |
Output is correct |
2 |
Correct |
676 ms |
29740 KB |
Output is correct |
3 |
Correct |
712 ms |
30116 KB |
Output is correct |
4 |
Correct |
813 ms |
28408 KB |
Output is correct |
5 |
Correct |
648 ms |
28408 KB |
Output is correct |
6 |
Correct |
933 ms |
29684 KB |
Output is correct |
7 |
Correct |
653 ms |
29404 KB |
Output is correct |
8 |
Correct |
677 ms |
29460 KB |
Output is correct |
9 |
Correct |
715 ms |
27968 KB |
Output is correct |
10 |
Correct |
652 ms |
27384 KB |
Output is correct |
11 |
Correct |
228 ms |
18808 KB |
Output is correct |
12 |
Correct |
622 ms |
28256 KB |
Output is correct |
13 |
Correct |
842 ms |
30328 KB |
Output is correct |
14 |
Correct |
662 ms |
28792 KB |
Output is correct |
15 |
Correct |
690 ms |
28664 KB |
Output is correct |
16 |
Correct |
650 ms |
28864 KB |
Output is correct |
17 |
Correct |
672 ms |
28792 KB |
Output is correct |
18 |
Correct |
692 ms |
29820 KB |
Output is correct |
19 |
Correct |
682 ms |
28824 KB |
Output is correct |
20 |
Correct |
684 ms |
28772 KB |
Output is correct |
21 |
Correct |
726 ms |
28792 KB |
Output is correct |
22 |
Correct |
660 ms |
28892 KB |
Output is correct |
23 |
Correct |
231 ms |
19576 KB |
Output is correct |
24 |
Correct |
672 ms |
29916 KB |
Output is correct |
25 |
Correct |
33 ms |
7160 KB |
Output is correct |
26 |
Correct |
7 ms |
5112 KB |
Output is correct |
27 |
Correct |
7 ms |
5112 KB |
Output is correct |
28 |
Correct |
58 ms |
9196 KB |
Output is correct |
29 |
Correct |
35 ms |
7544 KB |
Output is correct |
30 |
Correct |
8 ms |
5240 KB |
Output is correct |
31 |
Correct |
9 ms |
5368 KB |
Output is correct |
32 |
Correct |
11 ms |
5368 KB |
Output is correct |
33 |
Correct |
8 ms |
5240 KB |
Output is correct |
34 |
Correct |
39 ms |
7544 KB |
Output is correct |
35 |
Correct |
8 ms |
5112 KB |
Output is correct |
36 |
Correct |
7 ms |
5108 KB |
Output is correct |
37 |
Correct |
7 ms |
5112 KB |
Output is correct |
38 |
Correct |
8 ms |
5280 KB |
Output is correct |
39 |
Correct |
7 ms |
5116 KB |
Output is correct |
40 |
Correct |
879 ms |
29420 KB |
Output is correct |
41 |
Correct |
896 ms |
28552 KB |
Output is correct |
42 |
Correct |
898 ms |
28280 KB |
Output is correct |
43 |
Correct |
343 ms |
20600 KB |
Output is correct |
44 |
Correct |
253 ms |
20652 KB |
Output is correct |
45 |
Correct |
636 ms |
27344 KB |
Output is correct |
46 |
Correct |
646 ms |
27128 KB |
Output is correct |
47 |
Correct |
893 ms |
28672 KB |
Output is correct |
48 |
Correct |
354 ms |
20088 KB |
Output is correct |
49 |
Correct |
742 ms |
27688 KB |
Output is correct |
50 |
Correct |
638 ms |
27084 KB |
Output is correct |
51 |
Correct |
607 ms |
27256 KB |
Output is correct |