이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int N = 100000;
const long long inf = 200000000000000;
long long d[4][N];
vector<array<long long, 2>> adj[N];
vector<int> adjDAG[N];
long long dp[N][4];
/*
d[0] : Shortest distance from S
d[1] : Shortest distance from T
d[2] : Shortest distance from U
d[3] : Shortest distance from V
*/
void initArrays(int n) {
for (int i = 0; i < n; i++) {
d[0][i] = d[1][i] = d[2][i] = d[3][i] = inf;
}
for (int id = 0; id < n; id++) {
for (int j = 0; j < 4; j++) {
dp[id][j] = -1;
}
}
return ;
}
void runDijkstra(int u, int id) {
priority_queue<array<long long, 2>, vector<array<long long, 2>>, greater<array<long long, 2>>> pQue;
d[id][u] = 0;
pQue.push({d[id][u], u});
while (!pQue.empty()) {
auto t = pQue.top();
pQue.pop();
if (t[0] != d[id][t[1]]) {
continue;
}
for (auto x : adj[t[1]]) {
if (d[id][x[0]] > t[0] + x[1]) {
d[id][x[0]] = t[0] + x[1];
pQue.push({d[id][x[0]], x[0]});
}
}
}
return ;
}
long long DP(int u, int id) {
if (dp[u][id] != -1) {
return dp[u][id];
}
long long res = d[id][u];
for (auto x : adjDAG[u]) {
res = min(res, DP(x, id));
}
return dp[u][id] = res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
initArrays(n);
int s, t;
cin >> s >> t;
--s, --t;
int u, v;
cin >> u >> v;
--u, --v;
vector<array<int, 3>> edges;
for (int i = 0; i < m; i++) {
int x, y, z;
cin >> x >> y >> z;
--x, --y;
adj[x].push_back({y, z});
adj[y].push_back({x, z});
edges.push_back({x, y, z});
}
runDijkstra(s, 0);
runDijkstra(t, 1);
runDijkstra(u, 2);
runDijkstra(v, 3);
long long cCost = d[0][t];
for (int i = 0; i < m; i++) {
int x = edges[i][0];
int y = edges[i][1];
int z = edges[i][2];
if (d[0][x] + z + d[1][y] == cCost) {
adjDAG[x].push_back(y);
} else if (d[0][y] + z + d[1][x] == cCost) {
adjDAG[y].push_back(x);
}
}
long long res = inf;
for (int i = 0; i < n; i++) {
// u->i->midPoint->v
long long uToi = d[2][i] + DP(i, 3);
// v->i->midPoint->u
long long vToi = d[3][i] + DP(i, 2);
res = min(res, uToi);
res = min(res, vToi);
}
res = min(res, d[2][v]);
cout << res << '\n';
return 0;
}
# | 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... |