이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define x first
#define y second
#define int i64
using namespace std;
using i64 = long long;
using pii = pair<int, int>;
using pll = pair<i64, i64>;
const int N = 1e5 + 5;
vector<pii> g[N];
vector<int> dag[N];
i64 dist[N], dist_fst[N], dist_snd[N], dp[N][3];
int reach[N], in_deg[N];
vector<int> topsort;
int n, m, src, snk, fst, snd;
static void dijkstra(int nod, i64 dist[N]) {
priority_queue<pll> pq;
memset(dist, 0x3f, N * sizeof(i64));
dist[nod] = 0;
pq.emplace(dist[nod], nod);
while (!pq.empty()) {
i64 dst = -pq.top().x;
int u = pq.top().y;
pq.pop();
if (dst != dist[u])
continue;
for (auto v: g[u]) if (dist[v.x] > dst + v.y) {
dist[v.x] = dst + v.y;
pq.emplace(-dist[v.x], v.x); } } }
static void make_dag() {
function<void(int)> dfs1 = [&](int u) {
reach[u] = 1;
for (auto v: g[u])
if (reach[v.x] == 0 && dist[u] - v.y == dist[v.x])
dfs1(v.x); };
function<void(int)> dfs2 = [&](int u) {
reach[u] = 2;
for (auto v: g[u])
if (reach[v.x] == 1 && dist[u] + v.y == dist[v.x]) {
dfs2(v.x);
dag[u].push_back(v.x); } };
dfs1(snk);
dfs2(src); }
static void make_topsort() {
function<void(int)> dfs = [&](int u) {
for (auto v: dag[u]) if (--in_deg[v] == 0)
dfs(v);
topsort.push_back(u); };
for (int u = 1; u <= n; ++u)
for (auto v: dag[u])
in_deg[v]+= 1;
topsort.reserve(n);
dfs(src); }
static void get_dp() {
for (auto u: topsort) {
dp[u][0] = dist_fst[u];
dp[u][1] = dist_snd[u];
dp[u][2] = dist_fst[u] + dist_snd[u];
for (auto v: dag[u]) {
// fst
dp[u][0] = min(dp[u][0], dp[v][0]);
// snd
dp[u][1] = min(dp[u][1], dp[v][1]);
// both
dp[u][2] = min(dp[u][2], dp[v][2]);
dp[u][2] = min(dp[u][2], dp[v][0] + dist_snd[u]);
dp[u][2] = min(dp[u][2], dp[v][1] + dist_fst[u]); } } }
main() {
#ifdef HOME
freopen("joi_commuter.in", "r", stdin);
freopen("joi_commuter.out", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m;
cin >> src >> snk;
cin >> fst >> snd;
for (int u, v, c, i = 0; i < m; ++i) {
cin >> u >> v >> c;
g[u].emplace_back(v, c);
g[v].emplace_back(u, c); }
dijkstra(src, dist);
dijkstra(fst, dist_fst);
dijkstra(snd, dist_snd);
make_dag();
make_topsort();
get_dp();
cout << min(dist_fst[snd], dp[src][2]) << '\n';
return 0; }
컴파일 시 표준 에러 (stderr) 메시지
commuter_pass.cpp:87:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main() {
^
# | 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... |