#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb emplace_back
#define ppb pop_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vll;
mt19937 rng(time(0));
#define maxn 100005
int n,m,s,t,u,v,a,b,c,on[maxn];
bool vis[maxn];
ll ans,ds[maxn],dt[maxn],du[maxn],dv[maxn],fu[maxn],fv[maxn];
vii AL[maxn];
vi AL2[maxn];
priority_queue<pll,vector<pll>,greater<pll>> pq;
void dij(int s,ll *dist){
for(int i=1;i<=n;++i)dist[i]=LINF;
dist[s]=0;pq.push({0,s});
while(!pq.empty()){
ll d;int u;tie(d,u)=pq.top();pq.pop();
if(d>dist[u])continue;
for(ii pr:AL[u]){
if(d+pr.se<dist[pr.fi]){
dist[pr.fi]=d+pr.se;
pq.push({dist[pr.fi],pr.fi});
}
}
}
}
void dfs(int u){
if(vis[u])return;
vis[u]=1;
fu[u]=du[u];fv[u]=dv[u];
for(int v:AL2[u]){
dfs(v);
mnto(fu[u],fu[v]);
mnto(fv[u],fv[v]);
}
mnto(ans,fu[u]+dv[u]);
mnto(ans,fv[u]+du[u]);
}
int main(){
sf("%d%d",&n,&m);
sf("%d%d",&s,&t);
sf("%d%d",&u,&v);
for(int i=0;i<m;++i){
sf("%d%d%d",&a,&b,&c);
AL[a].pb(b,c);
AL[b].pb(a,c);
}
dij(s,ds);dij(t,dt);
dij(u,du);dij(v,dv);
for(int i=1;i<=n;++i){
for(ii pr:AL[i]){
if(ds[i]+pr.se+dt[pr.fi]==ds[t]){
AL2[i].pb(pr.fi);
}
}
}
ans=du[v];
dfs(s);
pf("%lld\n",ans);
}
Compilation message
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:71:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
71 | sf("%d%d",&n,&m);
| ^
commuter_pass.cpp:72:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
72 | sf("%d%d",&s,&t);
| ^
commuter_pass.cpp:73:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
73 | sf("%d%d",&u,&v);
| ^
commuter_pass.cpp:75:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
75 | sf("%d%d%d",&a,&b,&c);
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
409 ms |
19576 KB |
Output is correct |
2 |
Correct |
373 ms |
20864 KB |
Output is correct |
3 |
Correct |
346 ms |
26416 KB |
Output is correct |
4 |
Correct |
327 ms |
20444 KB |
Output is correct |
5 |
Correct |
301 ms |
21344 KB |
Output is correct |
6 |
Correct |
331 ms |
19684 KB |
Output is correct |
7 |
Correct |
340 ms |
22128 KB |
Output is correct |
8 |
Correct |
358 ms |
21756 KB |
Output is correct |
9 |
Correct |
319 ms |
19740 KB |
Output is correct |
10 |
Correct |
285 ms |
19640 KB |
Output is correct |
11 |
Correct |
126 ms |
18904 KB |
Output is correct |
12 |
Correct |
423 ms |
19764 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
355 ms |
22804 KB |
Output is correct |
2 |
Correct |
353 ms |
22772 KB |
Output is correct |
3 |
Correct |
320 ms |
22240 KB |
Output is correct |
4 |
Correct |
366 ms |
22676 KB |
Output is correct |
5 |
Correct |
393 ms |
23256 KB |
Output is correct |
6 |
Correct |
329 ms |
25768 KB |
Output is correct |
7 |
Correct |
395 ms |
26084 KB |
Output is correct |
8 |
Correct |
393 ms |
22704 KB |
Output is correct |
9 |
Correct |
397 ms |
23280 KB |
Output is correct |
10 |
Correct |
332 ms |
22308 KB |
Output is correct |
11 |
Correct |
151 ms |
20808 KB |
Output is correct |
12 |
Correct |
330 ms |
26168 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
6092 KB |
Output is correct |
2 |
Correct |
4 ms |
5012 KB |
Output is correct |
3 |
Correct |
4 ms |
5068 KB |
Output is correct |
4 |
Correct |
19 ms |
7156 KB |
Output is correct |
5 |
Correct |
12 ms |
6040 KB |
Output is correct |
6 |
Correct |
4 ms |
5068 KB |
Output is correct |
7 |
Correct |
6 ms |
5148 KB |
Output is correct |
8 |
Correct |
6 ms |
5196 KB |
Output is correct |
9 |
Correct |
4 ms |
5068 KB |
Output is correct |
10 |
Correct |
12 ms |
6112 KB |
Output is correct |
11 |
Correct |
3 ms |
5068 KB |
Output is correct |
12 |
Correct |
4 ms |
5004 KB |
Output is correct |
13 |
Correct |
4 ms |
5068 KB |
Output is correct |
14 |
Correct |
4 ms |
5068 KB |
Output is correct |
15 |
Correct |
4 ms |
5016 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
409 ms |
19576 KB |
Output is correct |
2 |
Correct |
373 ms |
20864 KB |
Output is correct |
3 |
Correct |
346 ms |
26416 KB |
Output is correct |
4 |
Correct |
327 ms |
20444 KB |
Output is correct |
5 |
Correct |
301 ms |
21344 KB |
Output is correct |
6 |
Correct |
331 ms |
19684 KB |
Output is correct |
7 |
Correct |
340 ms |
22128 KB |
Output is correct |
8 |
Correct |
358 ms |
21756 KB |
Output is correct |
9 |
Correct |
319 ms |
19740 KB |
Output is correct |
10 |
Correct |
285 ms |
19640 KB |
Output is correct |
11 |
Correct |
126 ms |
18904 KB |
Output is correct |
12 |
Correct |
423 ms |
19764 KB |
Output is correct |
13 |
Correct |
355 ms |
22804 KB |
Output is correct |
14 |
Correct |
353 ms |
22772 KB |
Output is correct |
15 |
Correct |
320 ms |
22240 KB |
Output is correct |
16 |
Correct |
366 ms |
22676 KB |
Output is correct |
17 |
Correct |
393 ms |
23256 KB |
Output is correct |
18 |
Correct |
329 ms |
25768 KB |
Output is correct |
19 |
Correct |
395 ms |
26084 KB |
Output is correct |
20 |
Correct |
393 ms |
22704 KB |
Output is correct |
21 |
Correct |
397 ms |
23280 KB |
Output is correct |
22 |
Correct |
332 ms |
22308 KB |
Output is correct |
23 |
Correct |
151 ms |
20808 KB |
Output is correct |
24 |
Correct |
330 ms |
26168 KB |
Output is correct |
25 |
Correct |
12 ms |
6092 KB |
Output is correct |
26 |
Correct |
4 ms |
5012 KB |
Output is correct |
27 |
Correct |
4 ms |
5068 KB |
Output is correct |
28 |
Correct |
19 ms |
7156 KB |
Output is correct |
29 |
Correct |
12 ms |
6040 KB |
Output is correct |
30 |
Correct |
4 ms |
5068 KB |
Output is correct |
31 |
Correct |
6 ms |
5148 KB |
Output is correct |
32 |
Correct |
6 ms |
5196 KB |
Output is correct |
33 |
Correct |
4 ms |
5068 KB |
Output is correct |
34 |
Correct |
12 ms |
6112 KB |
Output is correct |
35 |
Correct |
3 ms |
5068 KB |
Output is correct |
36 |
Correct |
4 ms |
5004 KB |
Output is correct |
37 |
Correct |
4 ms |
5068 KB |
Output is correct |
38 |
Correct |
4 ms |
5068 KB |
Output is correct |
39 |
Correct |
4 ms |
5016 KB |
Output is correct |
40 |
Correct |
311 ms |
19848 KB |
Output is correct |
41 |
Correct |
323 ms |
19632 KB |
Output is correct |
42 |
Correct |
312 ms |
19740 KB |
Output is correct |
43 |
Correct |
169 ms |
21256 KB |
Output is correct |
44 |
Correct |
150 ms |
21260 KB |
Output is correct |
45 |
Correct |
415 ms |
22752 KB |
Output is correct |
46 |
Correct |
329 ms |
22456 KB |
Output is correct |
47 |
Correct |
314 ms |
20392 KB |
Output is correct |
48 |
Correct |
147 ms |
18628 KB |
Output is correct |
49 |
Correct |
251 ms |
19456 KB |
Output is correct |
50 |
Correct |
336 ms |
22124 KB |
Output is correct |
51 |
Correct |
324 ms |
22660 KB |
Output is correct |