#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define ll long long
#define FOR(i,a,b) for(int i = a ; i < b ; ++i)
const int N = 1e5 + 1;
const ll inf = 1e15;
typedef pair<ll,ll> ii;
vector<ii> g[N];
ll fS[N], fT[N];
ll fU[N], fV[N];
int deg[N];
void dijkstra(int S,ll *d) {
FOR(i,1,N) d[i] = inf;
priority_queue<ii,vector<ii>,greater<ii> > pq;
d[S] = 0;
pq.push(ii(0,S));
while (pq.size()) {
int u = pq.top().Y;
ll du = pq.top().X;
pq.pop();
if (du != d[u])
continue;
for(ii e : g[u]) {
int v = e.X;
int C = e.Y;
if (d[v] > du + C) {
d[v] = du + C;
pq.push({d[v],v});
}
}
}
}
ll dp1[N];
ll dp2[N];
ll ans = inf;
vector<int> fr[N];
vector<int> to[N];
void dfs(int u) {
dp1[u] = fU[u];
dp2[u] = fV[u];
for(int v : to[u]) dp1[u] = min(dp1[u],dp1[v]);
for(int v : to[u]) dp2[u] = min(dp2[u],dp2[v]);
for(int v : fr[u]) {
deg[v]--;
if (deg[v] == 0)
dfs(v);
}
ans = min(ans,dp1[u] + fV[u]);
ans = min(ans,dp2[u] + fU[u]);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n, m; cin >> n >> m;
int S, T; cin >> S >> T;
int U, V; cin >> U >> V;
FOR(i,0,m) {
int x; cin >> x;
int y; cin >> y;
int c; cin >> c;
g[x].push_back(ii(y,c));
g[y].push_back(ii(x,c));
}
dijkstra(S,fS);
dijkstra(T,fT);
dijkstra(U,fU);
dijkstra(V,fV);
FOR(i,1,n + 1)
for(ii e : g[i]) {
int v = e.X;
int C = e.Y;
if (fS[i] + fT[v] + C == fS[T])
fr[i].push_back(v),
to[v].push_back(i),
deg[v]++;
}
dfs(S); cout << min(ans,fU[V]) << endl;
}
/*
8 8
5 7
6 8
1 2 2
2 3 3
3 4 4
1 4 1
1 5 5
2 6 6
3 7 7
4 8 8
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
412 ms |
24100 KB |
Output is correct |
2 |
Correct |
417 ms |
24148 KB |
Output is correct |
3 |
Correct |
447 ms |
28520 KB |
Output is correct |
4 |
Correct |
404 ms |
24156 KB |
Output is correct |
5 |
Correct |
431 ms |
25600 KB |
Output is correct |
6 |
Correct |
423 ms |
24116 KB |
Output is correct |
7 |
Correct |
475 ms |
26236 KB |
Output is correct |
8 |
Correct |
457 ms |
25852 KB |
Output is correct |
9 |
Correct |
404 ms |
22756 KB |
Output is correct |
10 |
Correct |
340 ms |
22596 KB |
Output is correct |
11 |
Correct |
208 ms |
21408 KB |
Output is correct |
12 |
Correct |
429 ms |
22896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
446 ms |
24808 KB |
Output is correct |
2 |
Correct |
440 ms |
25180 KB |
Output is correct |
3 |
Correct |
430 ms |
24564 KB |
Output is correct |
4 |
Correct |
437 ms |
25080 KB |
Output is correct |
5 |
Correct |
451 ms |
25592 KB |
Output is correct |
6 |
Correct |
458 ms |
27704 KB |
Output is correct |
7 |
Correct |
476 ms |
28400 KB |
Output is correct |
8 |
Correct |
458 ms |
25292 KB |
Output is correct |
9 |
Correct |
466 ms |
25780 KB |
Output is correct |
10 |
Correct |
510 ms |
24976 KB |
Output is correct |
11 |
Correct |
211 ms |
23288 KB |
Output is correct |
12 |
Correct |
483 ms |
28328 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
11896 KB |
Output is correct |
2 |
Correct |
11 ms |
10488 KB |
Output is correct |
3 |
Correct |
11 ms |
10492 KB |
Output is correct |
4 |
Correct |
31 ms |
13176 KB |
Output is correct |
5 |
Correct |
20 ms |
11896 KB |
Output is correct |
6 |
Correct |
18 ms |
10744 KB |
Output is correct |
7 |
Correct |
12 ms |
10616 KB |
Output is correct |
8 |
Correct |
13 ms |
10744 KB |
Output is correct |
9 |
Correct |
13 ms |
10620 KB |
Output is correct |
10 |
Correct |
22 ms |
11896 KB |
Output is correct |
11 |
Correct |
11 ms |
10616 KB |
Output is correct |
12 |
Correct |
11 ms |
10488 KB |
Output is correct |
13 |
Correct |
11 ms |
10488 KB |
Output is correct |
14 |
Correct |
11 ms |
10616 KB |
Output is correct |
15 |
Correct |
11 ms |
10616 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
412 ms |
24100 KB |
Output is correct |
2 |
Correct |
417 ms |
24148 KB |
Output is correct |
3 |
Correct |
447 ms |
28520 KB |
Output is correct |
4 |
Correct |
404 ms |
24156 KB |
Output is correct |
5 |
Correct |
431 ms |
25600 KB |
Output is correct |
6 |
Correct |
423 ms |
24116 KB |
Output is correct |
7 |
Correct |
475 ms |
26236 KB |
Output is correct |
8 |
Correct |
457 ms |
25852 KB |
Output is correct |
9 |
Correct |
404 ms |
22756 KB |
Output is correct |
10 |
Correct |
340 ms |
22596 KB |
Output is correct |
11 |
Correct |
208 ms |
21408 KB |
Output is correct |
12 |
Correct |
429 ms |
22896 KB |
Output is correct |
13 |
Correct |
446 ms |
24808 KB |
Output is correct |
14 |
Correct |
440 ms |
25180 KB |
Output is correct |
15 |
Correct |
430 ms |
24564 KB |
Output is correct |
16 |
Correct |
437 ms |
25080 KB |
Output is correct |
17 |
Correct |
451 ms |
25592 KB |
Output is correct |
18 |
Correct |
458 ms |
27704 KB |
Output is correct |
19 |
Correct |
476 ms |
28400 KB |
Output is correct |
20 |
Correct |
458 ms |
25292 KB |
Output is correct |
21 |
Correct |
466 ms |
25780 KB |
Output is correct |
22 |
Correct |
510 ms |
24976 KB |
Output is correct |
23 |
Correct |
211 ms |
23288 KB |
Output is correct |
24 |
Correct |
483 ms |
28328 KB |
Output is correct |
25 |
Correct |
21 ms |
11896 KB |
Output is correct |
26 |
Correct |
11 ms |
10488 KB |
Output is correct |
27 |
Correct |
11 ms |
10492 KB |
Output is correct |
28 |
Correct |
31 ms |
13176 KB |
Output is correct |
29 |
Correct |
20 ms |
11896 KB |
Output is correct |
30 |
Correct |
18 ms |
10744 KB |
Output is correct |
31 |
Correct |
12 ms |
10616 KB |
Output is correct |
32 |
Correct |
13 ms |
10744 KB |
Output is correct |
33 |
Correct |
13 ms |
10620 KB |
Output is correct |
34 |
Correct |
22 ms |
11896 KB |
Output is correct |
35 |
Correct |
11 ms |
10616 KB |
Output is correct |
36 |
Correct |
11 ms |
10488 KB |
Output is correct |
37 |
Correct |
11 ms |
10488 KB |
Output is correct |
38 |
Correct |
11 ms |
10616 KB |
Output is correct |
39 |
Correct |
11 ms |
10616 KB |
Output is correct |
40 |
Correct |
379 ms |
23676 KB |
Output is correct |
41 |
Correct |
406 ms |
22692 KB |
Output is correct |
42 |
Correct |
404 ms |
22940 KB |
Output is correct |
43 |
Correct |
224 ms |
25336 KB |
Output is correct |
44 |
Correct |
252 ms |
25336 KB |
Output is correct |
45 |
Correct |
507 ms |
28584 KB |
Output is correct |
46 |
Correct |
513 ms |
28492 KB |
Output is correct |
47 |
Correct |
414 ms |
23984 KB |
Output is correct |
48 |
Correct |
251 ms |
24184 KB |
Output is correct |
49 |
Correct |
341 ms |
23580 KB |
Output is correct |
50 |
Correct |
470 ms |
27216 KB |
Output is correct |
51 |
Correct |
487 ms |
28468 KB |
Output is correct |