이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int N = 100001;
vector<array<int, 2>> adj[N], dag[N];
int n;
void dijkstra(int s, long long *dist) {
priority_queue<array<long long, 2>> queue;
fill(dist, dist + n + 1, LLONG_MAX);
queue.push({0, s});
dist[s] = 0;
while (!queue.empty()) {
auto [d, u] = queue.top();
queue.pop();
d = -d;
if (d > dist[u]) {
continue;
}
for (auto [c, w] : adj[u]) {
if (d + w < dist[c]) {
dist[c] = d + w;
queue.push({-dist[c], c});
}
}
}
}
long long dist[3][N];
long long solve(int s, int t) {
priority_queue<array<long long, 3>> queue;
for (int i = 0; i < 3; ++i) {
fill(dist[i], dist[i] + n + 1, LLONG_MAX);
}
queue.push({0, s, 0});
dist[0][s] = 0;
while (!queue.empty()) {
auto [d, u, k] = queue.top();
queue.pop();
d = -d;
if (d > dist[k][u]) {
continue;
}
if (k < 2 && d < dist[k + 1][u]) {
dist[k + 1][u] = d;
queue.push(array<long long, 3>{-d, u, k + 1});
}
for (auto [c, w] : (k == 1 ? dag[u] : adj[u])) {
if (d + w < dist[k][c]) {
dist[k][c] = d + w;
queue.push(array<long long, 3>{-dist[k][c], c, k});
}
}
}
return dist[2][t];
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int m, s, t, x, y;
cin >> n >> m >> s >> t >> x >> y;
while (m--) {
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
dijkstra(s, dist[0]);
dijkstra(t, dist[1]);
for (int i = 1; i <= n; ++i) {
for (auto [j, w] : adj[i]) {
if (dist[0][i] + w + dist[1][j] == dist[0][t]) {
dag[i].push_back({j, 0});
}
}
}
cout << min(solve(x, y), solve(y, x)) << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |