#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int MXN = 100005;
// int n, m, s, t, u, v, father[MXN], du[MXN], dv[MXN], uu = LLONG_MAX, vv = LLONG_MAX;
// int n, m, s, t, u, v, ds[MXN], du[MXN], dv[MXN], ans = LLONG_MAX, uu = LLONG_MAX, vv = LLONG_MAX;
// vector<pii> edge[MXN];
// vector<int> path, father[MXN];
// set<int> reach[MXN];
// bool B = false;
// bitset<MXN> b;
int n, m, s, t, u, v, du[MXN], dv[MXN], ds[MXN], ans = LLONG_MAX, dp[2][MXN];
vector<pii> edge[MXN];
vector<int> path, father[MXN];
bitset<MXN> b;
vector<int> R[MXN], L[MXN];
void GET_PATH() {
b.reset();
priority_queue<pair<int, pii>, vector<pair<int, pii>>, greater<pair<int, pii>>> pq;
pq.push({0, {s, s}});
while (pq.size()) {
pair<int, pii> now = pq.top();
pq.pop();
if (b[now.second.second]) {
if (ds[now.second.second] == now.first) father[now.second.second].push_back(now.second.first);
continue;
}
b[now.second.second] = true;
ds[now.second.second] = now.first;
father[now.second.second].push_back(now.second.first);
for (auto &i : edge[now.second.second]) {
if (b[i.first]) continue;
pq.push({now.first + i.second, {now.second.second, i.first}});
}
}
b.reset();
queue<int> q;
q.push(t);
while (q.size()) {
int now = q.front();
q.pop();
if (b[now]) continue;
b[now] = true;
path.push_back(now);
for (auto &i : father[now]) {
if (i == now) continue;
if (b[i]) continue;
L[now].push_back(i);
R[i].push_back(now);
q.push(i);
}
}
}
void DIJKSTRA(int start, int *arr) {
b.reset();
priority_queue<pii, vector<pii>, greater<pii>> pq;
pq.push({0, start});
while (pq.size()) {
pii now = pq.top();
pq.pop();
if (b[now.second]) continue;
b[now.second] = true;
arr[now.second] = now.first;
for (auto &i : edge[now.second]) {
if (b[i.first]) continue;
pq.push({now.first + i.second, i.first});
}
}
}
// void GET_REACH(int id) {
// queue<int> q;
// q.push(id);
// while (q.size()) {
// int now = q.front();
// q.pop();
// // if (b[now]) {
// // continue;
// // }
// // b[now] = true;
// if (!reach[id].insert(now).second) continue;
// // path.push_back(now);
// for (auto &i : father[now]) {
// q.push(i);
// }
// }
// }
void BFS() {
queue<int> q;
q.push(s);
while (q.size()) {
int now = q.front();
q.pop();
dp[0][now] = LLONG_MAX;
dp[1][now] = LLONG_MAX;
for (auto &i : L[now]) {
dp[0][now] = min(dp[0][now], dp[0][i]);
dp[1][now] = min(dp[1][now], dp[1][i]);
}
dp[0][now] = min(dp[0][now], du[now]);
dp[1][now] = min(dp[1][now], dv[now]);
ans = min(ans, min(dp[0][now] + dv[now], dp[1][now] + du[now]));
for (auto &i : R[now]) q.push(i);
}
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int x, y, z;
cin >> n >> m >> s >> t >> u >> v;
for (int i = 0; i < m; i++) {
cin >> x >> y >> z;
edge[x].push_back({y, z});
edge[y].push_back({x, z});
}
GET_PATH();
DIJKSTRA(u, du);
DIJKSTRA(v, dv);
// for (int i = 1; i <= n; i++) {
// cout << R[i].size() << ' ';
// for (auto &j : R[i]) cout << j << ' ';
// cout << endl;
// }
// cout << endl;
// for (int i = 1; i <= n; i++) {
// cout << L[i].size() << ' ';
// for (auto &j : L[i]) cout << j << ' ';
// cout << endl;
// }
ans = du[v];
BFS();
cout << ans << endl;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
9684 KB |
Output is correct |
2 |
Correct |
5 ms |
9724 KB |
Output is correct |
3 |
Correct |
7 ms |
9684 KB |
Output is correct |
4 |
Correct |
5 ms |
9684 KB |
Output is correct |
5 |
Correct |
5 ms |
9684 KB |
Output is correct |
6 |
Incorrect |
5 ms |
9684 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
9684 KB |
Output is correct |
2 |
Correct |
5 ms |
9724 KB |
Output is correct |
3 |
Correct |
7 ms |
9684 KB |
Output is correct |
4 |
Correct |
5 ms |
9684 KB |
Output is correct |
5 |
Correct |
5 ms |
9684 KB |
Output is correct |
6 |
Incorrect |
5 ms |
9684 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
9684 KB |
Output is correct |
2 |
Correct |
5 ms |
9724 KB |
Output is correct |
3 |
Correct |
7 ms |
9684 KB |
Output is correct |
4 |
Correct |
5 ms |
9684 KB |
Output is correct |
5 |
Correct |
5 ms |
9684 KB |
Output is correct |
6 |
Incorrect |
5 ms |
9684 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |