#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <tuple>
template <class T>
using MinHeap = std::priority_queue<T, std::vector<T>, std::greater<T>>;
using lint = long long;
constexpr lint INF = 1LL << 50;
struct Edge {
int dst;
lint cost;
explicit Edge(int dst, lint cost) : dst(dst), cost(cost) {}
};
using Graph = std::vector<std::vector<Edge>>;
std::vector<lint> dijkstra(const Graph& graph, int r) {
std::vector<lint> dist(graph.size(), INF);
dist[r] = 0;
MinHeap<std::pair<lint, int>> que;
que.emplace(dist[r], r);
while (!que.empty()) {
lint d;
int v;
std::tie(d, v) = que.top();
que.pop();
if (dist[v] < d) continue;
for (auto e : graph[v]) {
int u = e.dst;
lint nd = d + e.cost;
if (dist[u] > nd) {
dist[u] = nd;
que.emplace(nd, u);
}
}
}
return dist;
}
void solve() {
int n, m, s, t, a, b;
std::cin >> n >> m >> s >> t >> a >> b;
--s, --t, --a, --b;
Graph graph(n);
while (m--) {
int u, v;
lint c;
std::cin >> u >> v >> c;
--u, --v;
graph[u].emplace_back(v, c);
graph[v].emplace_back(u, c);
}
auto ds = dijkstra(graph, s),
da = dijkstra(graph, a),
db = dijkstra(graph, b);
std::vector<int> vs(n);
std::iota(vs.begin(), vs.end(), 0);
std::sort(vs.begin(), vs.end(),
[&](int u, int v) { return ds[u] < ds[v]; });
std::vector<std::vector<lint>>
dist(3, std::vector<lint>(n, INF));
for (auto v : vs) {
dist[0][v] = da[v];
dist[1][v] = db[v];
dist[2][v] = da[v] + db[v];
for (auto e : graph[v]) {
int u = e.dst;
if (ds[u] + e.cost > ds[v]) continue;
for (int k = 0; k < 3; ++k) {
dist[k][v] = std::min(dist[k][v], dist[k][u]);
}
}
dist[2][v] = std::min({dist[2][v],
dist[0][v] + db[v],
dist[1][v] + da[v]});
}
std::cout << std::min(da[b], dist[2][t]) << std::endl;
}
int main() {
std::cin.tie(nullptr);
std::cout.tie(nullptr);
std::ios::sync_with_stdio(false);
solve();
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
230 ms |
18908 KB |
Output is correct |
2 |
Correct |
252 ms |
18896 KB |
Output is correct |
3 |
Correct |
248 ms |
18808 KB |
Output is correct |
4 |
Correct |
251 ms |
18844 KB |
Output is correct |
5 |
Correct |
247 ms |
18872 KB |
Output is correct |
6 |
Correct |
259 ms |
18852 KB |
Output is correct |
7 |
Correct |
239 ms |
18864 KB |
Output is correct |
8 |
Correct |
249 ms |
18800 KB |
Output is correct |
9 |
Correct |
238 ms |
18884 KB |
Output is correct |
10 |
Correct |
201 ms |
23292 KB |
Output is correct |
11 |
Correct |
103 ms |
15876 KB |
Output is correct |
12 |
Correct |
262 ms |
23064 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
236 ms |
18892 KB |
Output is correct |
2 |
Correct |
261 ms |
18932 KB |
Output is correct |
3 |
Correct |
244 ms |
18900 KB |
Output is correct |
4 |
Correct |
258 ms |
19176 KB |
Output is correct |
5 |
Correct |
248 ms |
18944 KB |
Output is correct |
6 |
Correct |
235 ms |
18800 KB |
Output is correct |
7 |
Correct |
248 ms |
18888 KB |
Output is correct |
8 |
Correct |
266 ms |
18920 KB |
Output is correct |
9 |
Correct |
253 ms |
18944 KB |
Output is correct |
10 |
Correct |
243 ms |
18880 KB |
Output is correct |
11 |
Correct |
120 ms |
13764 KB |
Output is correct |
12 |
Correct |
237 ms |
22760 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
1664 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
12 ms |
3020 KB |
Output is correct |
5 |
Correct |
6 ms |
1612 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
460 KB |
Output is correct |
8 |
Correct |
2 ms |
460 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
6 ms |
1612 KB |
Output is correct |
11 |
Correct |
0 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
320 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
230 ms |
18908 KB |
Output is correct |
2 |
Correct |
252 ms |
18896 KB |
Output is correct |
3 |
Correct |
248 ms |
18808 KB |
Output is correct |
4 |
Correct |
251 ms |
18844 KB |
Output is correct |
5 |
Correct |
247 ms |
18872 KB |
Output is correct |
6 |
Correct |
259 ms |
18852 KB |
Output is correct |
7 |
Correct |
239 ms |
18864 KB |
Output is correct |
8 |
Correct |
249 ms |
18800 KB |
Output is correct |
9 |
Correct |
238 ms |
18884 KB |
Output is correct |
10 |
Correct |
201 ms |
23292 KB |
Output is correct |
11 |
Correct |
103 ms |
15876 KB |
Output is correct |
12 |
Correct |
262 ms |
23064 KB |
Output is correct |
13 |
Correct |
236 ms |
18892 KB |
Output is correct |
14 |
Correct |
261 ms |
18932 KB |
Output is correct |
15 |
Correct |
244 ms |
18900 KB |
Output is correct |
16 |
Correct |
258 ms |
19176 KB |
Output is correct |
17 |
Correct |
248 ms |
18944 KB |
Output is correct |
18 |
Correct |
235 ms |
18800 KB |
Output is correct |
19 |
Correct |
248 ms |
18888 KB |
Output is correct |
20 |
Correct |
266 ms |
18920 KB |
Output is correct |
21 |
Correct |
253 ms |
18944 KB |
Output is correct |
22 |
Correct |
243 ms |
18880 KB |
Output is correct |
23 |
Correct |
120 ms |
13764 KB |
Output is correct |
24 |
Correct |
237 ms |
22760 KB |
Output is correct |
25 |
Correct |
10 ms |
1664 KB |
Output is correct |
26 |
Correct |
1 ms |
332 KB |
Output is correct |
27 |
Correct |
1 ms |
332 KB |
Output is correct |
28 |
Correct |
12 ms |
3020 KB |
Output is correct |
29 |
Correct |
6 ms |
1612 KB |
Output is correct |
30 |
Correct |
1 ms |
332 KB |
Output is correct |
31 |
Correct |
1 ms |
460 KB |
Output is correct |
32 |
Correct |
2 ms |
460 KB |
Output is correct |
33 |
Correct |
1 ms |
332 KB |
Output is correct |
34 |
Correct |
6 ms |
1612 KB |
Output is correct |
35 |
Correct |
0 ms |
332 KB |
Output is correct |
36 |
Correct |
1 ms |
332 KB |
Output is correct |
37 |
Correct |
1 ms |
320 KB |
Output is correct |
38 |
Correct |
1 ms |
332 KB |
Output is correct |
39 |
Correct |
1 ms |
364 KB |
Output is correct |
40 |
Correct |
236 ms |
22264 KB |
Output is correct |
41 |
Correct |
240 ms |
23020 KB |
Output is correct |
42 |
Correct |
240 ms |
23204 KB |
Output is correct |
43 |
Correct |
109 ms |
15996 KB |
Output is correct |
44 |
Correct |
102 ms |
15820 KB |
Output is correct |
45 |
Correct |
253 ms |
22332 KB |
Output is correct |
46 |
Correct |
229 ms |
22020 KB |
Output is correct |
47 |
Correct |
234 ms |
22648 KB |
Output is correct |
48 |
Correct |
112 ms |
15224 KB |
Output is correct |
49 |
Correct |
191 ms |
21888 KB |
Output is correct |
50 |
Correct |
235 ms |
22276 KB |
Output is correct |
51 |
Correct |
210 ms |
22260 KB |
Output is correct |