#include <bits/stdc++.h>
#define int long long
using namespace std;
const int nmax = 1e5 + 1;
vector<vector<pair<int, int>>> adj;
int n;
int pz[nmax], pt[nmax];
vector<int> calc(int a) {
set<pair<int, int>> s;
s.insert({0, a});
vector<int> v(n + 1, 1e18);
v[a] = 0;
while(!s.empty()) {
auto curr = s.begin();
int sum = (*curr).first, i = (*curr).second;
s.erase(*curr);
if(v[i] < sum) {
continue;
}
for(auto it : adj[i]) {
if(v[it.first] > it.second + sum) {
v[it.first] = it.second + sum;
s.insert({it.second + sum, it.first});
}
}
}
return v;
}
int32_t main() {
int m;
cin >> n >> m;
int A, B, C, D;
cin >> A >> B >> C >> D;
adj.resize(n + 1);
for(int i = 1; i <= m; i++) {
int a, b, c;
cin >> a >> b >> c;
adj[a].push_back({b, c});
adj[b].push_back({a, c});
}
vector<int> x = calc(A);
vector<int> y = calc(B);
vector<int> z = calc(C);
vector<int> t = calc(D);
vector<pair<int, int>> vp;
for(int i = 1; i <= n; i++) {
if(x[i] + y[i] == x[B]) {
vp.push_back({x[i], i});
}
}
sort(vp.begin(), vp.end());
int ans = z[D];
for(auto i1 : vp) {
int i = i1.second;
pz[i] = z[i];
pt[i] = t[i];
for(auto it : adj[i]) {
if(x[it.first] + it.second == x[i]) {
pz[i] = min(pz[i], pz[it.first]);
pt[i] = min(pt[i], pt[it.first]);
}
}
ans = min(ans, pz[i] + t[i]);
ans = min(ans, pt[i] + z[i]);
}
cout << ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
422 ms |
24040 KB |
Output is correct |
2 |
Correct |
381 ms |
24404 KB |
Output is correct |
3 |
Correct |
357 ms |
25232 KB |
Output is correct |
4 |
Correct |
414 ms |
24148 KB |
Output is correct |
5 |
Correct |
359 ms |
24892 KB |
Output is correct |
6 |
Correct |
446 ms |
24560 KB |
Output is correct |
7 |
Correct |
381 ms |
25076 KB |
Output is correct |
8 |
Correct |
358 ms |
25068 KB |
Output is correct |
9 |
Correct |
403 ms |
23348 KB |
Output is correct |
10 |
Correct |
320 ms |
22984 KB |
Output is correct |
11 |
Correct |
150 ms |
15268 KB |
Output is correct |
12 |
Correct |
360 ms |
23468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
440 ms |
24704 KB |
Output is correct |
2 |
Correct |
379 ms |
24148 KB |
Output is correct |
3 |
Correct |
410 ms |
24428 KB |
Output is correct |
4 |
Correct |
396 ms |
24216 KB |
Output is correct |
5 |
Correct |
383 ms |
25016 KB |
Output is correct |
6 |
Correct |
359 ms |
25168 KB |
Output is correct |
7 |
Correct |
389 ms |
25448 KB |
Output is correct |
8 |
Correct |
382 ms |
24184 KB |
Output is correct |
9 |
Correct |
394 ms |
24900 KB |
Output is correct |
10 |
Correct |
393 ms |
24320 KB |
Output is correct |
11 |
Correct |
120 ms |
15688 KB |
Output is correct |
12 |
Correct |
347 ms |
24920 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
2136 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
27 ms |
3940 KB |
Output is correct |
5 |
Correct |
14 ms |
2140 KB |
Output is correct |
6 |
Correct |
2 ms |
348 KB |
Output is correct |
7 |
Correct |
2 ms |
604 KB |
Output is correct |
8 |
Correct |
3 ms |
600 KB |
Output is correct |
9 |
Correct |
2 ms |
348 KB |
Output is correct |
10 |
Correct |
14 ms |
2040 KB |
Output is correct |
11 |
Correct |
1 ms |
344 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
422 ms |
24040 KB |
Output is correct |
2 |
Correct |
381 ms |
24404 KB |
Output is correct |
3 |
Correct |
357 ms |
25232 KB |
Output is correct |
4 |
Correct |
414 ms |
24148 KB |
Output is correct |
5 |
Correct |
359 ms |
24892 KB |
Output is correct |
6 |
Correct |
446 ms |
24560 KB |
Output is correct |
7 |
Correct |
381 ms |
25076 KB |
Output is correct |
8 |
Correct |
358 ms |
25068 KB |
Output is correct |
9 |
Correct |
403 ms |
23348 KB |
Output is correct |
10 |
Correct |
320 ms |
22984 KB |
Output is correct |
11 |
Correct |
150 ms |
15268 KB |
Output is correct |
12 |
Correct |
360 ms |
23468 KB |
Output is correct |
13 |
Correct |
440 ms |
24704 KB |
Output is correct |
14 |
Correct |
379 ms |
24148 KB |
Output is correct |
15 |
Correct |
410 ms |
24428 KB |
Output is correct |
16 |
Correct |
396 ms |
24216 KB |
Output is correct |
17 |
Correct |
383 ms |
25016 KB |
Output is correct |
18 |
Correct |
359 ms |
25168 KB |
Output is correct |
19 |
Correct |
389 ms |
25448 KB |
Output is correct |
20 |
Correct |
382 ms |
24184 KB |
Output is correct |
21 |
Correct |
394 ms |
24900 KB |
Output is correct |
22 |
Correct |
393 ms |
24320 KB |
Output is correct |
23 |
Correct |
120 ms |
15688 KB |
Output is correct |
24 |
Correct |
347 ms |
24920 KB |
Output is correct |
25 |
Correct |
15 ms |
2136 KB |
Output is correct |
26 |
Correct |
1 ms |
344 KB |
Output is correct |
27 |
Correct |
1 ms |
348 KB |
Output is correct |
28 |
Correct |
27 ms |
3940 KB |
Output is correct |
29 |
Correct |
14 ms |
2140 KB |
Output is correct |
30 |
Correct |
2 ms |
348 KB |
Output is correct |
31 |
Correct |
2 ms |
604 KB |
Output is correct |
32 |
Correct |
3 ms |
600 KB |
Output is correct |
33 |
Correct |
2 ms |
348 KB |
Output is correct |
34 |
Correct |
14 ms |
2040 KB |
Output is correct |
35 |
Correct |
1 ms |
344 KB |
Output is correct |
36 |
Correct |
1 ms |
348 KB |
Output is correct |
37 |
Correct |
1 ms |
348 KB |
Output is correct |
38 |
Correct |
1 ms |
348 KB |
Output is correct |
39 |
Correct |
1 ms |
460 KB |
Output is correct |
40 |
Correct |
471 ms |
25624 KB |
Output is correct |
41 |
Correct |
439 ms |
23644 KB |
Output is correct |
42 |
Correct |
492 ms |
23608 KB |
Output is correct |
43 |
Correct |
124 ms |
16320 KB |
Output is correct |
44 |
Correct |
128 ms |
16388 KB |
Output is correct |
45 |
Correct |
338 ms |
24400 KB |
Output is correct |
46 |
Correct |
366 ms |
24344 KB |
Output is correct |
47 |
Correct |
424 ms |
24656 KB |
Output is correct |
48 |
Correct |
127 ms |
15820 KB |
Output is correct |
49 |
Correct |
375 ms |
25280 KB |
Output is correct |
50 |
Correct |
317 ms |
24540 KB |
Output is correct |
51 |
Correct |
313 ms |
24396 KB |
Output is correct |