| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 591593 | piOOE | Olympic Bus (JOI20_ho_t4) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200, M = 50000;
const ll infL = 3e18;
bool in_s_to_all[M], in_n_to_all[M], in_all_to_s[M], in_all_to_n[M], used[N];
ll dist_s_to_all[N], dist_n_to_all[N], dist_all_to_s[N], dist_all_to_n[N], D_s_all[N], D_all_s[N], D_n_all[N], D_all_n[N], ;
int A[M], B[M], W[M], D[M], P[M], revP[M], n, m;
vector<pair<int, int>> newg[N];
vector<int> now;
void dfs(int v) {
used[v] = true;
for (auto [to, i]: newg[v]) {
if (!used[to]) {
now.push_back(i);
dfs(to);
}
}
}
void dijkstra(int s, vector<pair<int, int>> g[], ll dist[], bool need, bool in[]) {
fill(dist, dist + n, infL);
dist[s] = 0;
set<pair<ll, int>> st;
st.insert({0, s});
while (!st.empty()) {
auto [ww, x] = *st.begin();
st.erase(st.begin());
for (auto [to, i]: g[x]) {
if (dist[to] > dist[x] + W[i]) {
st.erase({dist[to], to});
dist[to] = dist[x] + W[i];
st.insert({dist[to], to});
}
}
}
if (need) {
for (int i = 0; i < n; ++i) {
newg[i].clear();
}
for (int i = 0; i < n; ++i) {
for (auto [to, j]: g[i]) {
if (dist[to] == dist[i] + W[j]) {
newg[i].emplace_back(to, j);
}
}
}
memset(used, 0, sizeof(used[0]) * n);
now.clear();
now.reserve(n - 1);
dfs(s);
for (int i : now) {
in[i] = true;
}
}
}
vector<pair<int, int>> g[N], revg[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 0; i < m; ++i) {
cin >> A[i] >> B[i] >> W[i] >> D[i];
--A[i], --B[i];
P[i] = (int) g[A[i]].size();
revP[i] = (int) revg[B[i]].size();
g[A[i]].emplace_back(B[i], i);
revg[B[i]].emplace_back(A[i], i);
}
dijkstra(0, g, dist_s_to_all, true, in_s_to_all);
dijkstra(0, revg, dist_all_to_s, true, in_all_to_s);
dijkstra(n - 1, g, dist_n_to_all, true, in_n_to_all);
dijkstra(n - 1, revg, dist_all_to_n, true, in_all_to_n);
ll ans = infL;
ans = min(ans, dist_s_to_all[n - 1] + dist_n_to_all[0]);
for (int i = 0; i < m; ++i) {
{
swap(g[A[i]][P[i]], g[A[i]].back());
g[A[i]].pop_back();
g[B[i]].emplace_back(A[i], i);
}
{
swap(revg[B[i]][revP[i]], revg[B[i]].back());
revg[B[i]].pop_back();
revg[A[i]].emplace_back(B[i], i);
}
if (in_s_to_all[i])
dijkstra(0, g, D_s_all, false, in_s_to_all);
else
memcpy(D_s_all, dist_s_to_all, sizeof(D_s_all));
if (in_all_to_s[i])
dijkstra(0, revg, D_all_s, false, in_all_to_s);
else
memcpy(D_all_s, dist_all_to_s, sizeof(D_s_all));
if (in_n_to_all[i])
dijkstra(n - 1, g, D_n_all, false, in_n_to_all);
else
memcpy(D_n_all, dist_n_to_all, sizeof(D_s_all));
if (in_all_to_n[i])
dijkstra(n - 1, revg, D_all_n, false, in_all_to_n);
else
memcpy(D_all_n, dist_all_to_n, sizeof(D_s_all));
ans = min(ans, D[i] + min(D_s_all[n - 1], D_s_all[B[i]] + W[i] + D_all_n[A[i]]) +
min(D_n_all[0], D_n_all[B[i]] + W[i] + D_all_s[A[i]]));
{
g[A[i]].emplace_back(B[i], i);
swap(g[A[i]][P[i]], g[A[i]].back());
g[B[i]].pop_back();
}
{
revg[B[i]].emplace_back(A[i], i);
swap(revg[B[i]][revP[i]], revg[B[i]].back());
revg[A[i]].pop_back();
}
}
cout << (ans == infL ? -1 : ans);
return 0;
}