이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define DEBUG(x) //x
#define A(x) DEBUG(assert(x))
#define PRINT(x) DEBUG(cerr << x)
#define PV(x) DEBUG(cerr << #x << " = " << x << endl)
#define PAR(x) DEBUG(PRINT(#x << " = { "); for (auto y : x) PRINT(y << ' '); PRINT("}\n");)
#define PAR2(x) DEBUG(PRINT(#x << " = { "); for (auto [y, z] : x) PRINT(y << ',' << z << " "); PRINT("}\n");)
typedef int64_t i64;
const i64 INF = 1e18; //1000000007; //998244353;
struct S {
i64 n, m, s, t, u, v, ans;
vector<vector<pair<i64, i64>>> edges;
vector<i64> ds, du, dv, dpu, dpv;
array<vector<vector<i64>>, 2> sp;
void run() {
cin >> n >> m >> s >> t >> u >> v;
--s; --t; --u; --v;
edges.resize(n);
for (int i = 0; i < m; ++i) {
i64 a, b, c;
cin >> a >> b >> c;
--a; --b;
edges[a].push_back({b, c});
edges[b].push_back({a, c});
}
sp[0].resize(n);
sp[1].resize(n);
ds = dijkstra(s, 0);
du = dijkstra(u, 1);
dv = dijkstra(v, 1);
ans = du[v];
dpu.resize(n);
dpv.resize(n);
bfs(s, t, 0);
bfs(t, s, 1);
cout << ans << '\n';
}
void bfs(i64 start, i64 end, int order) {
fill(dpu.begin(), dpu.end(), INF);
fill(dpv.begin(), dpv.end(), INF);
queue<i64> q;
vector<bool> visited(n, false);
visited[start] = true;
q.push(start);
while (!q.empty()) {
i64 node = q.front();
q.pop();
dpu[node] = du[node];
dpv[node] = dv[node];
for (auto prev : sp[order][node]) {
dpu[node] = min(dpu[node], dpu[prev]);
dpv[node] = min(dpv[node], dpv[prev]);
}
for (auto next : sp[order^1][node]) {
if (!visited[next]) {
visited[next] = true;
q.push(next);
}
}
}
ans = min(ans, dpu[end] + dpv[end]);
}
vector<i64> dijkstra(i64 start, int run) {
vector<i64> d(n, INF);
d[start] = 0;
vector<bool> visited(n, false);
priority_queue<pair<i64, i64>> q;
q.push({0, start});
while (!q.empty()) {
i64 dist = q.top().first;
i64 node = q.top().second;
q.pop();
if (visited[node]) continue;
visited[node] = true;
for (auto [next, wt] : edges[node]) {
if (d[node] + wt <= d[next]) {
if (run == 0) {
sp[0][next].push_back(node);
sp[1][node].push_back(next);
}
d[next] = d[node] + wt;
q.push({-d[node] - wt, next});
}
}
}
return d;
}
};
int main() {
ios::sync_with_stdio(0); cin.tie(0);
auto sol = make_unique<S>();
sol->run();
}
컴파일 시 표준 에러 (stderr) 메시지
commuter_pass.cpp: In member function 'std::vector<long int> S::dijkstra(i64, int)':
commuter_pass.cpp:79:11: warning: unused variable 'dist' [-Wunused-variable]
79 | i64 dist = q.top().first;
| ^~~~
# | 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... |