#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define ep emplace_back
using namespace std;
typedef pair<int, int> ii;
const int maxN = 1e5 + 5;
const int inf = 100;
int n,m,s,t,u,v;
int distU[maxN], distV[maxN], distS[maxN], distT[maxN], dU[maxN], dV[maxN];
int deg[maxN];
vector<ii> adj[maxN];
void dijkstra(int s, long long *dist){
priority_queue<ii, vector<ii>, greater<ii>> pq;
dist[s] = 0;
pq.push({0,s});
while(!pq.empty()){
int d = pq.top().first;
int v = pq.top().se;
pq.pop();
if(d > dist[v]) continue;
for(ii &p : adj[v])
if(d + p.se < dist[p.fi]){
dist[p.fi] = d + p.se;
pq.push({dist[p.fi],p.fi});
}
}
}
int32_t main ()
{
ios_base::sync_with_stdio(false); cin.tie(); cout.tie();
cin >> n >> m >> s >> t >> u >> v;
for(int i = 1; i <= m; ++i){
int a,b,c;
cin >> a >> b >> c;
adj[a].ep(b,c);
adj[b].ep(a,c);
}
memset(distU, inf, sizeof distU);
memset(distV, inf, sizeof distV);
memset(distS, inf, sizeof distS);
memset(distT, inf, sizeof distT);
dijkstra(u, distU);
dijkstra(v, distV);
dijkstra(s, distS);
dijkstra(t, distT);
for (int i = 1; i <= n; ++i) {
dU[i] = distU[i];
dV[i] = distV[i];
if (distS[i] + distT[i] == distS[t]){
for (ii p : adj[i])
if (distS[i] + p.se == distS[p.fi] && distS[p.fi] + distT[p.fi] == distS[t])
++deg[p.fi];
}
}
queue<int> q;
q.push(s);
while(!q.empty()){
int cur = q.front();
q.pop();
for(ii p : adj[cur])
if(distS[cur] + p.se == distS[p.fi] && distS[p.fi] + distT[p.fi] == distS[t]){
dU[p.fi] = min(dU[p.fi],dU[cur]);
dV[p.fi] = min(dV[p.fi],dV[cur]);
if(!(--deg[p.fi]))
q.push(p.fi);
}
}
int res = 1e18;
for (int i = 1; i <= n; ++i)
res = min({res, dU[i] + distV[i], dV[i] + distU[i]});
//cout << res << endl;
printf("%lld", res);
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
368 ms |
19516 KB |
Output is correct |
2 |
Correct |
372 ms |
18864 KB |
Output is correct |
3 |
Correct |
377 ms |
19508 KB |
Output is correct |
4 |
Correct |
354 ms |
20212 KB |
Output is correct |
5 |
Correct |
362 ms |
18824 KB |
Output is correct |
6 |
Correct |
367 ms |
19556 KB |
Output is correct |
7 |
Correct |
371 ms |
18960 KB |
Output is correct |
8 |
Correct |
369 ms |
18712 KB |
Output is correct |
9 |
Correct |
362 ms |
18184 KB |
Output is correct |
10 |
Correct |
325 ms |
22504 KB |
Output is correct |
11 |
Correct |
153 ms |
15480 KB |
Output is correct |
12 |
Correct |
384 ms |
22332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
394 ms |
18872 KB |
Output is correct |
2 |
Correct |
402 ms |
18796 KB |
Output is correct |
3 |
Correct |
382 ms |
18816 KB |
Output is correct |
4 |
Correct |
391 ms |
18972 KB |
Output is correct |
5 |
Correct |
399 ms |
18808 KB |
Output is correct |
6 |
Correct |
379 ms |
19028 KB |
Output is correct |
7 |
Correct |
390 ms |
18816 KB |
Output is correct |
8 |
Correct |
400 ms |
19104 KB |
Output is correct |
9 |
Correct |
384 ms |
18792 KB |
Output is correct |
10 |
Correct |
392 ms |
18816 KB |
Output is correct |
11 |
Correct |
162 ms |
13556 KB |
Output is correct |
12 |
Correct |
389 ms |
22452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
7296 KB |
Output is correct |
2 |
Correct |
4 ms |
5888 KB |
Output is correct |
3 |
Correct |
4 ms |
5888 KB |
Output is correct |
4 |
Correct |
20 ms |
8576 KB |
Output is correct |
5 |
Correct |
12 ms |
7296 KB |
Output is correct |
6 |
Correct |
5 ms |
6016 KB |
Output is correct |
7 |
Correct |
5 ms |
6016 KB |
Output is correct |
8 |
Correct |
6 ms |
6144 KB |
Output is correct |
9 |
Correct |
5 ms |
6016 KB |
Output is correct |
10 |
Correct |
17 ms |
7296 KB |
Output is correct |
11 |
Correct |
4 ms |
5888 KB |
Output is correct |
12 |
Correct |
4 ms |
5888 KB |
Output is correct |
13 |
Correct |
4 ms |
5888 KB |
Output is correct |
14 |
Correct |
5 ms |
5888 KB |
Output is correct |
15 |
Correct |
5 ms |
5888 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
368 ms |
19516 KB |
Output is correct |
2 |
Correct |
372 ms |
18864 KB |
Output is correct |
3 |
Correct |
377 ms |
19508 KB |
Output is correct |
4 |
Correct |
354 ms |
20212 KB |
Output is correct |
5 |
Correct |
362 ms |
18824 KB |
Output is correct |
6 |
Correct |
367 ms |
19556 KB |
Output is correct |
7 |
Correct |
371 ms |
18960 KB |
Output is correct |
8 |
Correct |
369 ms |
18712 KB |
Output is correct |
9 |
Correct |
362 ms |
18184 KB |
Output is correct |
10 |
Correct |
325 ms |
22504 KB |
Output is correct |
11 |
Correct |
153 ms |
15480 KB |
Output is correct |
12 |
Correct |
384 ms |
22332 KB |
Output is correct |
13 |
Correct |
394 ms |
18872 KB |
Output is correct |
14 |
Correct |
402 ms |
18796 KB |
Output is correct |
15 |
Correct |
382 ms |
18816 KB |
Output is correct |
16 |
Correct |
391 ms |
18972 KB |
Output is correct |
17 |
Correct |
399 ms |
18808 KB |
Output is correct |
18 |
Correct |
379 ms |
19028 KB |
Output is correct |
19 |
Correct |
390 ms |
18816 KB |
Output is correct |
20 |
Correct |
400 ms |
19104 KB |
Output is correct |
21 |
Correct |
384 ms |
18792 KB |
Output is correct |
22 |
Correct |
392 ms |
18816 KB |
Output is correct |
23 |
Correct |
162 ms |
13556 KB |
Output is correct |
24 |
Correct |
389 ms |
22452 KB |
Output is correct |
25 |
Correct |
13 ms |
7296 KB |
Output is correct |
26 |
Correct |
4 ms |
5888 KB |
Output is correct |
27 |
Correct |
4 ms |
5888 KB |
Output is correct |
28 |
Correct |
20 ms |
8576 KB |
Output is correct |
29 |
Correct |
12 ms |
7296 KB |
Output is correct |
30 |
Correct |
5 ms |
6016 KB |
Output is correct |
31 |
Correct |
5 ms |
6016 KB |
Output is correct |
32 |
Correct |
6 ms |
6144 KB |
Output is correct |
33 |
Correct |
5 ms |
6016 KB |
Output is correct |
34 |
Correct |
17 ms |
7296 KB |
Output is correct |
35 |
Correct |
4 ms |
5888 KB |
Output is correct |
36 |
Correct |
4 ms |
5888 KB |
Output is correct |
37 |
Correct |
4 ms |
5888 KB |
Output is correct |
38 |
Correct |
5 ms |
5888 KB |
Output is correct |
39 |
Correct |
5 ms |
5888 KB |
Output is correct |
40 |
Correct |
348 ms |
23292 KB |
Output is correct |
41 |
Correct |
351 ms |
22388 KB |
Output is correct |
42 |
Correct |
354 ms |
22544 KB |
Output is correct |
43 |
Correct |
172 ms |
15480 KB |
Output is correct |
44 |
Correct |
180 ms |
15608 KB |
Output is correct |
45 |
Correct |
358 ms |
22356 KB |
Output is correct |
46 |
Correct |
364 ms |
21936 KB |
Output is correct |
47 |
Correct |
359 ms |
23292 KB |
Output is correct |
48 |
Correct |
185 ms |
14968 KB |
Output is correct |
49 |
Correct |
293 ms |
22792 KB |
Output is correct |
50 |
Correct |
362 ms |
22308 KB |
Output is correct |
51 |
Correct |
343 ms |
22056 KB |
Output is correct |