#include "bits/stdc++.h"
using namespace std;
#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif
using T = pair<long long, int>;
const int N = 1e5 + 5;
const long long INF = 1e16;
int n, m;
vector<pair<int, int>> g[N];
vector<long long> dij(int src) {
vector<long long> ret(n + 1, INF);
ret[src] = 0;
priority_queue<T, vector<T>, greater<T>> pq;
pq.emplace(0, src);
while (!pq.empty()) {
auto [c, v] = pq.top();
pq.pop();
if (c != ret[v]) {
continue;
}
for (auto [u, w] : g[v]) {
if (w + c < ret[u]) {
ret[u] = w + c;
pq.emplace(ret[u], u);
}
}
}
return ret;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
int s, t;
cin >> s >> t;
int qu, qv;
cin >> qu >> qv;
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
g[u].emplace_back(v, w);
g[v].emplace_back(u, w);
}
vector<long long> ds = dij(s);
vector<long long> dt = dij(t);
vector<long long> dv = dij(qv);
vector<long long> du = dij(qu);
long long ans = du[qv];
for (int rep = 0; rep < 2; ++rep) {
vector<int> ord(n);
iota(ord.begin(), ord.end(), 1);
sort(ord.begin(), ord.end(), [&](int i, int j) {
return ds[i] < ds[j];
});
vector<long long> dp(n + 1, INF);
for (int v : ord) {
ans = min(ans, dp[v] + dv[v]);
for (auto [u, w] : g[v]) {
if (ds[v] + w + dt[u] == ds[t]) {
dp[u] = min({dp[u], dp[v], du[v]});
}
}
}
swap(qu, qv);
swap(du, dv);
}
cout << ans << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
174 ms |
19120 KB |
Output is correct |
2 |
Correct |
222 ms |
17576 KB |
Output is correct |
3 |
Correct |
185 ms |
17416 KB |
Output is correct |
4 |
Correct |
215 ms |
18072 KB |
Output is correct |
5 |
Correct |
185 ms |
17112 KB |
Output is correct |
6 |
Correct |
234 ms |
19108 KB |
Output is correct |
7 |
Correct |
214 ms |
17376 KB |
Output is correct |
8 |
Correct |
172 ms |
17552 KB |
Output is correct |
9 |
Correct |
238 ms |
18312 KB |
Output is correct |
10 |
Correct |
182 ms |
18068 KB |
Output is correct |
11 |
Correct |
64 ms |
12216 KB |
Output is correct |
12 |
Correct |
237 ms |
18008 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
189 ms |
17900 KB |
Output is correct |
2 |
Correct |
244 ms |
17468 KB |
Output is correct |
3 |
Correct |
249 ms |
17772 KB |
Output is correct |
4 |
Correct |
209 ms |
17340 KB |
Output is correct |
5 |
Correct |
191 ms |
17352 KB |
Output is correct |
6 |
Correct |
190 ms |
17504 KB |
Output is correct |
7 |
Correct |
254 ms |
17332 KB |
Output is correct |
8 |
Correct |
203 ms |
17332 KB |
Output is correct |
9 |
Correct |
215 ms |
17348 KB |
Output is correct |
10 |
Correct |
225 ms |
17332 KB |
Output is correct |
11 |
Correct |
81 ms |
12216 KB |
Output is correct |
12 |
Correct |
181 ms |
17560 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
3676 KB |
Output is correct |
2 |
Correct |
1 ms |
2652 KB |
Output is correct |
3 |
Correct |
1 ms |
2652 KB |
Output is correct |
4 |
Correct |
11 ms |
4740 KB |
Output is correct |
5 |
Correct |
6 ms |
3676 KB |
Output is correct |
6 |
Correct |
1 ms |
2652 KB |
Output is correct |
7 |
Correct |
2 ms |
2908 KB |
Output is correct |
8 |
Correct |
2 ms |
2908 KB |
Output is correct |
9 |
Correct |
1 ms |
2908 KB |
Output is correct |
10 |
Correct |
7 ms |
3676 KB |
Output is correct |
11 |
Correct |
1 ms |
2652 KB |
Output is correct |
12 |
Correct |
1 ms |
2652 KB |
Output is correct |
13 |
Correct |
1 ms |
2652 KB |
Output is correct |
14 |
Correct |
2 ms |
2648 KB |
Output is correct |
15 |
Correct |
1 ms |
2652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
174 ms |
19120 KB |
Output is correct |
2 |
Correct |
222 ms |
17576 KB |
Output is correct |
3 |
Correct |
185 ms |
17416 KB |
Output is correct |
4 |
Correct |
215 ms |
18072 KB |
Output is correct |
5 |
Correct |
185 ms |
17112 KB |
Output is correct |
6 |
Correct |
234 ms |
19108 KB |
Output is correct |
7 |
Correct |
214 ms |
17376 KB |
Output is correct |
8 |
Correct |
172 ms |
17552 KB |
Output is correct |
9 |
Correct |
238 ms |
18312 KB |
Output is correct |
10 |
Correct |
182 ms |
18068 KB |
Output is correct |
11 |
Correct |
64 ms |
12216 KB |
Output is correct |
12 |
Correct |
237 ms |
18008 KB |
Output is correct |
13 |
Correct |
189 ms |
17900 KB |
Output is correct |
14 |
Correct |
244 ms |
17468 KB |
Output is correct |
15 |
Correct |
249 ms |
17772 KB |
Output is correct |
16 |
Correct |
209 ms |
17340 KB |
Output is correct |
17 |
Correct |
191 ms |
17352 KB |
Output is correct |
18 |
Correct |
190 ms |
17504 KB |
Output is correct |
19 |
Correct |
254 ms |
17332 KB |
Output is correct |
20 |
Correct |
203 ms |
17332 KB |
Output is correct |
21 |
Correct |
215 ms |
17348 KB |
Output is correct |
22 |
Correct |
225 ms |
17332 KB |
Output is correct |
23 |
Correct |
81 ms |
12216 KB |
Output is correct |
24 |
Correct |
181 ms |
17560 KB |
Output is correct |
25 |
Correct |
6 ms |
3676 KB |
Output is correct |
26 |
Correct |
1 ms |
2652 KB |
Output is correct |
27 |
Correct |
1 ms |
2652 KB |
Output is correct |
28 |
Correct |
11 ms |
4740 KB |
Output is correct |
29 |
Correct |
6 ms |
3676 KB |
Output is correct |
30 |
Correct |
1 ms |
2652 KB |
Output is correct |
31 |
Correct |
2 ms |
2908 KB |
Output is correct |
32 |
Correct |
2 ms |
2908 KB |
Output is correct |
33 |
Correct |
1 ms |
2908 KB |
Output is correct |
34 |
Correct |
7 ms |
3676 KB |
Output is correct |
35 |
Correct |
1 ms |
2652 KB |
Output is correct |
36 |
Correct |
1 ms |
2652 KB |
Output is correct |
37 |
Correct |
1 ms |
2652 KB |
Output is correct |
38 |
Correct |
2 ms |
2648 KB |
Output is correct |
39 |
Correct |
1 ms |
2652 KB |
Output is correct |
40 |
Correct |
223 ms |
19584 KB |
Output is correct |
41 |
Correct |
196 ms |
18508 KB |
Output is correct |
42 |
Correct |
200 ms |
18232 KB |
Output is correct |
43 |
Correct |
65 ms |
12296 KB |
Output is correct |
44 |
Correct |
68 ms |
12352 KB |
Output is correct |
45 |
Correct |
220 ms |
17160 KB |
Output is correct |
46 |
Correct |
156 ms |
16732 KB |
Output is correct |
47 |
Correct |
176 ms |
18248 KB |
Output is correct |
48 |
Correct |
76 ms |
11692 KB |
Output is correct |
49 |
Correct |
182 ms |
19164 KB |
Output is correct |
50 |
Correct |
166 ms |
17276 KB |
Output is correct |
51 |
Correct |
210 ms |
17324 KB |
Output is correct |