#include <iostream>
#include <queue>
#include <limits>
using namespace std;
vector<pair<int, long long>> edges[100001];
long long u_distances[100001];
long long best_entry[100001];
long long best_finished[100001];
long long rbest_entry[100001];
long long rbest_finished[100001];
long long v_distances[100001];
long long s_distances[100001];
int n, m, s, t, u, v, a, b;
long long c;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> s >> t >> u >> v;
while (m--){
cin >> a >> b >> c;
edges[a].emplace_back(b, c);
edges[b].emplace_back(a, c);
}
for (int i = 1; i <= n; i++){
u_distances[i] = numeric_limits<long long>::max();
}
u_distances[u] = 0;
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> q1;
q1.emplace(0, u);
while (!q1.empty()){
long long d1 = q1.top().first;
long long node = q1.top().second;
q1.pop();
if (u_distances[node]!=d1){
continue;
}
for (auto [connected, length] : edges[node]){
if (d1 + length < u_distances[connected]){
u_distances[connected] = d1+length;
q1.emplace(d1+length, connected);
}
}
}
for (int i = 1; i <= n; i++){
v_distances[i] = numeric_limits<long long>::max();
}
v_distances[v] = 0;
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> q2;
q2.emplace(0, v);
while (!q2.empty()){
long long d1 = q2.top().first;
long long node = q2.top().second;
q2.pop();
if (v_distances[node]!=d1){
continue;
}
for (auto [connected, length] : edges[node]){
if (d1 + length < v_distances[connected]){
v_distances[connected] = d1+length;
q2.emplace(d1+length, connected);
}
}
}
for (int i = 1; i <= n; i++){
s_distances[i] = numeric_limits<long long>::max();
best_entry[i] = numeric_limits<long long>::max();
best_finished[i] = numeric_limits<long long>::max();
rbest_entry[i] = numeric_limits<long long>::max();
rbest_finished[i] = numeric_limits<long long>::max();
}
s_distances[s] = 0;
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> q3;
q3.emplace(0, s);
while (!q3.empty()){
long long d1 = q3.top().first;
long long node = q3.top().second;
q3.pop();
if (s_distances[node]!=d1){
continue;
}
best_entry[node] = min(best_entry[node], u_distances[node]);
best_finished[node] = min(best_finished[node], v_distances[node] + best_entry[node]);
rbest_entry[node] = min(rbest_entry[node], v_distances[node]);
rbest_finished[node] = min(rbest_finished[node], u_distances[node] + rbest_entry[node]);
for (auto [connected, length] : edges[node]){
if (d1 + length < s_distances[connected]){
s_distances[connected] = d1 + length;
q3.emplace(d1+length, connected);
best_entry[connected] = best_entry[node];
best_finished[connected] = best_finished[node];
rbest_entry[connected] = rbest_entry[node];
rbest_finished[connected] = rbest_finished[node];
}
else if (d1 + length == s_distances[connected]){
best_entry[connected] = min(best_entry[node], best_entry[connected]);
best_finished[connected] = min(best_finished[node], best_finished[connected]);
rbest_entry[connected] = min(rbest_entry[node], rbest_entry[connected]);
rbest_finished[connected] = min(rbest_finished[node], rbest_finished[connected]);
}
}
}
cout << min(min(best_finished[t], rbest_finished[t]), u_distances[v]);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
173 ms |
27596 KB |
Output is correct |
2 |
Correct |
169 ms |
25412 KB |
Output is correct |
3 |
Correct |
185 ms |
25152 KB |
Output is correct |
4 |
Correct |
167 ms |
26440 KB |
Output is correct |
5 |
Correct |
159 ms |
24936 KB |
Output is correct |
6 |
Correct |
174 ms |
27816 KB |
Output is correct |
7 |
Correct |
174 ms |
25312 KB |
Output is correct |
8 |
Correct |
178 ms |
25336 KB |
Output is correct |
9 |
Correct |
175 ms |
25928 KB |
Output is correct |
10 |
Correct |
168 ms |
25804 KB |
Output is correct |
11 |
Correct |
51 ms |
15448 KB |
Output is correct |
12 |
Correct |
181 ms |
25924 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
180 ms |
25760 KB |
Output is correct |
2 |
Correct |
193 ms |
25388 KB |
Output is correct |
3 |
Correct |
187 ms |
25416 KB |
Output is correct |
4 |
Correct |
237 ms |
25416 KB |
Output is correct |
5 |
Correct |
197 ms |
25216 KB |
Output is correct |
6 |
Correct |
212 ms |
25232 KB |
Output is correct |
7 |
Correct |
223 ms |
25156 KB |
Output is correct |
8 |
Correct |
183 ms |
25416 KB |
Output is correct |
9 |
Correct |
182 ms |
25416 KB |
Output is correct |
10 |
Correct |
185 ms |
25160 KB |
Output is correct |
11 |
Correct |
52 ms |
15440 KB |
Output is correct |
12 |
Correct |
167 ms |
25152 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
9816 KB |
Output is correct |
2 |
Correct |
2 ms |
8028 KB |
Output is correct |
3 |
Correct |
2 ms |
8028 KB |
Output is correct |
4 |
Correct |
12 ms |
11384 KB |
Output is correct |
5 |
Correct |
7 ms |
10072 KB |
Output is correct |
6 |
Correct |
3 ms |
8368 KB |
Output is correct |
7 |
Correct |
3 ms |
8280 KB |
Output is correct |
8 |
Correct |
3 ms |
8388 KB |
Output is correct |
9 |
Correct |
2 ms |
8116 KB |
Output is correct |
10 |
Correct |
7 ms |
9820 KB |
Output is correct |
11 |
Correct |
2 ms |
8028 KB |
Output is correct |
12 |
Correct |
2 ms |
8028 KB |
Output is correct |
13 |
Correct |
2 ms |
8024 KB |
Output is correct |
14 |
Correct |
2 ms |
8024 KB |
Output is correct |
15 |
Correct |
2 ms |
8116 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
173 ms |
27596 KB |
Output is correct |
2 |
Correct |
169 ms |
25412 KB |
Output is correct |
3 |
Correct |
185 ms |
25152 KB |
Output is correct |
4 |
Correct |
167 ms |
26440 KB |
Output is correct |
5 |
Correct |
159 ms |
24936 KB |
Output is correct |
6 |
Correct |
174 ms |
27816 KB |
Output is correct |
7 |
Correct |
174 ms |
25312 KB |
Output is correct |
8 |
Correct |
178 ms |
25336 KB |
Output is correct |
9 |
Correct |
175 ms |
25928 KB |
Output is correct |
10 |
Correct |
168 ms |
25804 KB |
Output is correct |
11 |
Correct |
51 ms |
15448 KB |
Output is correct |
12 |
Correct |
181 ms |
25924 KB |
Output is correct |
13 |
Correct |
180 ms |
25760 KB |
Output is correct |
14 |
Correct |
193 ms |
25388 KB |
Output is correct |
15 |
Correct |
187 ms |
25416 KB |
Output is correct |
16 |
Correct |
237 ms |
25416 KB |
Output is correct |
17 |
Correct |
197 ms |
25216 KB |
Output is correct |
18 |
Correct |
212 ms |
25232 KB |
Output is correct |
19 |
Correct |
223 ms |
25156 KB |
Output is correct |
20 |
Correct |
183 ms |
25416 KB |
Output is correct |
21 |
Correct |
182 ms |
25416 KB |
Output is correct |
22 |
Correct |
185 ms |
25160 KB |
Output is correct |
23 |
Correct |
52 ms |
15440 KB |
Output is correct |
24 |
Correct |
167 ms |
25152 KB |
Output is correct |
25 |
Correct |
7 ms |
9816 KB |
Output is correct |
26 |
Correct |
2 ms |
8028 KB |
Output is correct |
27 |
Correct |
2 ms |
8028 KB |
Output is correct |
28 |
Correct |
12 ms |
11384 KB |
Output is correct |
29 |
Correct |
7 ms |
10072 KB |
Output is correct |
30 |
Correct |
3 ms |
8368 KB |
Output is correct |
31 |
Correct |
3 ms |
8280 KB |
Output is correct |
32 |
Correct |
3 ms |
8388 KB |
Output is correct |
33 |
Correct |
2 ms |
8116 KB |
Output is correct |
34 |
Correct |
7 ms |
9820 KB |
Output is correct |
35 |
Correct |
2 ms |
8028 KB |
Output is correct |
36 |
Correct |
2 ms |
8028 KB |
Output is correct |
37 |
Correct |
2 ms |
8024 KB |
Output is correct |
38 |
Correct |
2 ms |
8024 KB |
Output is correct |
39 |
Correct |
2 ms |
8116 KB |
Output is correct |
40 |
Correct |
170 ms |
28044 KB |
Output is correct |
41 |
Correct |
183 ms |
26096 KB |
Output is correct |
42 |
Correct |
172 ms |
26184 KB |
Output is correct |
43 |
Correct |
58 ms |
15444 KB |
Output is correct |
44 |
Correct |
52 ms |
15632 KB |
Output is correct |
45 |
Correct |
161 ms |
24540 KB |
Output is correct |
46 |
Correct |
154 ms |
24396 KB |
Output is correct |
47 |
Correct |
170 ms |
26116 KB |
Output is correct |
48 |
Correct |
55 ms |
14936 KB |
Output is correct |
49 |
Correct |
163 ms |
27548 KB |
Output is correct |
50 |
Correct |
156 ms |
24944 KB |
Output is correct |
51 |
Correct |
148 ms |
24448 KB |
Output is correct |