#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define s second
#define f first
#define left (node<<1),l,((l+r)>>1)
#define right ((node<<1)|1),((l+r)>>1) + 1,r
#define pii pair <ll,int>
using namespace std;
const int N = 2e5 + 5;
const ll inf = 1e18;
vector <pii> g[N];
int id[N];
bool vis[N];
ll dis[7][N],dp[N],dd[N],lenst;
int n,s,t,u,v;
void go(int x,int idx){
id[x] = idx;
for (int i = 1; i <= n; i++)
dis[idx][i] = inf;
priority_queue <pii> pq;
dis[idx][x] = 0;
pq.push({0LL,x});
while (pq.size()){
ll d = -pq.top().f; int x = pq.top().s;
pq.pop();
if (dis[idx][x] != d) continue;
for (auto [to,w]: g[x]){
if (dis[idx][to] > dis[idx][x] + w) {
dis[idx][to] = d + w;
pq.push({-d-w,to});
}
}
}
}
void G(int x){
int idx = id[x];
for (int i= 1; i <= n; i++)
dd[i] = inf,dp[i] = inf,vis[i]=0;
priority_queue <pii> pq;
dd[x] = 0;
dp[x] = dis[id[v]][x];
pq.push({0LL,x});
while (pq.size()){
ll d = -pq.top().f; int x = pq.top().s;
pq.pop();
if (vis[x]) continue;
vis[x]=1;
for (auto [to,w]: g[x]){
if (dis[id[s]][to] + dis[id[t]][to] != lenst) continue;
if (dd[to] >= d + w){
dd[to] = d + w;
dp[to] = min({dp[x],dp[to], dis[id[v]][to]});
if (!vis[to]) pq.push({-d-w,to});
}
}
}
}
signed main() {
ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
int m;
cin>>n>>m;
cin>>s>>t>>u>>v;
for (int i= 1; i <= m; i++){
int a,b,c;
cin>>a>>b>>c;
g[a].pb({b,c});
g[b].pb({a,c});
}
go(s,1);
go(t,2);
go(u,3);
go(v,4);
ll ans = dis[id[u]][v];
lenst = dis[id[s]][t];
G(t);
for (int i= 1; i <= n; i++){
if (dis[id[s]][i] + dis[id[t]][i] != lenst) continue;
ans = min(ans, dp[i] + dis[id[u]][i]);
}
G(s);
for (int i = 1; i <= n; i++){
if (dis[id[s]][i] + dis[id[t]][i] != lenst) continue;
ans = min(ans,dp[i] + dis[id[u]][i]);
}
cout<<ans;
}
Compilation message
commuter_pass.cpp: In function 'void G(int)':
commuter_pass.cpp:44:6: warning: unused variable 'idx' [-Wunused-variable]
44 | int idx = id[x];
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
209 ms |
21656 KB |
Output is correct |
2 |
Correct |
243 ms |
20552 KB |
Output is correct |
3 |
Correct |
246 ms |
22164 KB |
Output is correct |
4 |
Correct |
189 ms |
21808 KB |
Output is correct |
5 |
Correct |
225 ms |
20840 KB |
Output is correct |
6 |
Correct |
215 ms |
21904 KB |
Output is correct |
7 |
Correct |
225 ms |
20672 KB |
Output is correct |
8 |
Correct |
213 ms |
20628 KB |
Output is correct |
9 |
Correct |
214 ms |
20576 KB |
Output is correct |
10 |
Correct |
191 ms |
20536 KB |
Output is correct |
11 |
Correct |
86 ms |
15300 KB |
Output is correct |
12 |
Correct |
201 ms |
20616 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
244 ms |
20648 KB |
Output is correct |
2 |
Correct |
235 ms |
20536 KB |
Output is correct |
3 |
Correct |
243 ms |
20452 KB |
Output is correct |
4 |
Correct |
237 ms |
20552 KB |
Output is correct |
5 |
Correct |
237 ms |
20760 KB |
Output is correct |
6 |
Correct |
226 ms |
21312 KB |
Output is correct |
7 |
Correct |
289 ms |
21264 KB |
Output is correct |
8 |
Correct |
242 ms |
20620 KB |
Output is correct |
9 |
Correct |
232 ms |
20788 KB |
Output is correct |
10 |
Correct |
220 ms |
20540 KB |
Output is correct |
11 |
Correct |
80 ms |
15188 KB |
Output is correct |
12 |
Correct |
248 ms |
21912 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
6660 KB |
Output is correct |
2 |
Correct |
4 ms |
5048 KB |
Output is correct |
3 |
Correct |
2 ms |
5076 KB |
Output is correct |
4 |
Correct |
12 ms |
8568 KB |
Output is correct |
5 |
Correct |
7 ms |
6700 KB |
Output is correct |
6 |
Correct |
3 ms |
5204 KB |
Output is correct |
7 |
Correct |
3 ms |
5160 KB |
Output is correct |
8 |
Correct |
4 ms |
5236 KB |
Output is correct |
9 |
Correct |
3 ms |
5204 KB |
Output is correct |
10 |
Correct |
9 ms |
6828 KB |
Output is correct |
11 |
Correct |
2 ms |
5076 KB |
Output is correct |
12 |
Correct |
2 ms |
5076 KB |
Output is correct |
13 |
Correct |
2 ms |
5076 KB |
Output is correct |
14 |
Correct |
3 ms |
5076 KB |
Output is correct |
15 |
Correct |
3 ms |
5164 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
209 ms |
21656 KB |
Output is correct |
2 |
Correct |
243 ms |
20552 KB |
Output is correct |
3 |
Correct |
246 ms |
22164 KB |
Output is correct |
4 |
Correct |
189 ms |
21808 KB |
Output is correct |
5 |
Correct |
225 ms |
20840 KB |
Output is correct |
6 |
Correct |
215 ms |
21904 KB |
Output is correct |
7 |
Correct |
225 ms |
20672 KB |
Output is correct |
8 |
Correct |
213 ms |
20628 KB |
Output is correct |
9 |
Correct |
214 ms |
20576 KB |
Output is correct |
10 |
Correct |
191 ms |
20536 KB |
Output is correct |
11 |
Correct |
86 ms |
15300 KB |
Output is correct |
12 |
Correct |
201 ms |
20616 KB |
Output is correct |
13 |
Correct |
244 ms |
20648 KB |
Output is correct |
14 |
Correct |
235 ms |
20536 KB |
Output is correct |
15 |
Correct |
243 ms |
20452 KB |
Output is correct |
16 |
Correct |
237 ms |
20552 KB |
Output is correct |
17 |
Correct |
237 ms |
20760 KB |
Output is correct |
18 |
Correct |
226 ms |
21312 KB |
Output is correct |
19 |
Correct |
289 ms |
21264 KB |
Output is correct |
20 |
Correct |
242 ms |
20620 KB |
Output is correct |
21 |
Correct |
232 ms |
20788 KB |
Output is correct |
22 |
Correct |
220 ms |
20540 KB |
Output is correct |
23 |
Correct |
80 ms |
15188 KB |
Output is correct |
24 |
Correct |
248 ms |
21912 KB |
Output is correct |
25 |
Correct |
10 ms |
6660 KB |
Output is correct |
26 |
Correct |
4 ms |
5048 KB |
Output is correct |
27 |
Correct |
2 ms |
5076 KB |
Output is correct |
28 |
Correct |
12 ms |
8568 KB |
Output is correct |
29 |
Correct |
7 ms |
6700 KB |
Output is correct |
30 |
Correct |
3 ms |
5204 KB |
Output is correct |
31 |
Correct |
3 ms |
5160 KB |
Output is correct |
32 |
Correct |
4 ms |
5236 KB |
Output is correct |
33 |
Correct |
3 ms |
5204 KB |
Output is correct |
34 |
Correct |
9 ms |
6828 KB |
Output is correct |
35 |
Correct |
2 ms |
5076 KB |
Output is correct |
36 |
Correct |
2 ms |
5076 KB |
Output is correct |
37 |
Correct |
2 ms |
5076 KB |
Output is correct |
38 |
Correct |
3 ms |
5076 KB |
Output is correct |
39 |
Correct |
3 ms |
5164 KB |
Output is correct |
40 |
Correct |
192 ms |
25436 KB |
Output is correct |
41 |
Correct |
208 ms |
24548 KB |
Output is correct |
42 |
Correct |
186 ms |
24712 KB |
Output is correct |
43 |
Correct |
73 ms |
17172 KB |
Output is correct |
44 |
Correct |
90 ms |
17140 KB |
Output is correct |
45 |
Correct |
248 ms |
25416 KB |
Output is correct |
46 |
Correct |
249 ms |
25128 KB |
Output is correct |
47 |
Correct |
206 ms |
25316 KB |
Output is correct |
48 |
Correct |
85 ms |
16612 KB |
Output is correct |
49 |
Correct |
166 ms |
25056 KB |
Output is correct |
50 |
Correct |
243 ms |
25264 KB |
Output is correct |
51 |
Correct |
266 ms |
25596 KB |
Output is correct |