| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 202739 | klimoza | Olympic Bus (JOI20_ho_t4) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <math.h>
#include <cmath>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <cassert>
#include <random>
#include <deque>
#include <bitset>
#include <string>
#include <queue>
#include <complex>
//#define int long long
#define mp(a, b) make_pair(a, b)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define endl '\n'
using namespace std;
typedef long long ll;
typedef long double ld;
mt19937 mrand(random_device{}());
double PI = acos((double)-1);
const double eps = 1e-8;
const ll inf0 = 1023 * 1024 * 1024;
const ll inf = inf0 * inf0;
//const ll mod = 1e9 + 7;
//const ll mod = 777777773;
const ll mod = 1e9 + 7;
const ll MOD = mod * mod;
void solve();
void scan();
signed main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#endif
cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
cout << fixed; cout.precision(15);
solve();
}
struct Edge {
int u, v;
ll c, d;
int i;
Edge() {}
Edge(int i, int u, int v, ll c, ll d) : u(u), v(v), c(c), d(d), i(i){}
};
const int N = 407;
vector<Edge> g[N];
ll d1[N], d2[N];
void djikstra(int s, ll* d) {
for (int i = 0; i < N; i++)
d[i] = inf;
d[s] = 0;
set<pair<ll, int>> f;
for (int i = 0; i < N; i++)
f.insert({ d[i], i });
while (!f.empty()) {
auto v = *f.begin();
f.erase(f.begin());
if (v.first == inf) break;
for (auto e : g[v.second]) {
if (d[e.v] > v.first + e.c) {
f.erase({ d[e.v],e.v });
d[e.v] = v.first + e.c;
f.insert({ d[e.v],e.v });
}
}
}
}
ll jopa[N][N];
void solve() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) jopa[i][j] = 0;
else jopa[i][j] = inf;
}
}
vector<Edge> ed(m);
for (int i = 0; i < m; i++) {
cin >> ed[i].u >> ed[i].v >> ed[i].c >> ed[i].d;
jopa[ed[i].u][ed[i].v] = min(jopa[ed[i].u][ed[i].v], ed[i].c);
ed[i].u--; ed[i].v--;
ed[i].i = i;
g[ed[i].u].push_back(ed[i]);
}
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (jopa[i][k] != inf && jopa[k][j] != inf && jopa[i][j] > jopa[i][k] + jopa[k][j])
jopa[i][j] = jopa[i][k] + jopa[k][j];
}
}
}
vector<ll> ds1(n, inf), ds2(n, inf);
vector<Edge> p1(n), p2(n);
ds1[0] = 0; ds2[n - 1] = 0;
set<pair<ll, int>> f;
for (int i = 0; i < n; i++)
f.insert({ ds1[i], i });
while (!f.empty()) {
auto v = *f.begin();
if (v.first == inf) break;
f.erase(f.begin());
for (auto e : g[v.second]) {
if (ds1[e.v] > v.first + e.c) {
f.erase({ ds1[e.v], e.v });
p1[e.v] = e;
ds1[e.v] = v.first + e.c;
f.insert({ ds1[e.v], e.v });
}
}
}
f.clear();
for (int i = 0; i < n; i++)
f.insert({ ds2[i], i });
while (!f.empty()) {
auto v = *f.begin();
if (v.first == inf) break;
f.erase(f.begin());
for (auto e : g[v.second]) {
if (ds2[e.v] > v.first + e.c) {
f.erase({ ds2[e.v], e.v });
p2[e.v] = e;
ds2[e.v] = v.first + e.c;
f.insert({ ds2[e.v], e.v });
}
}
}
ll ans = inf;
if (ds1[n - 1] != inf && ds2[0] != inf)
ans = ds1[n - 1] + ds2[0];
vector<int> tmp;
for (int i = 1; i < n; i++)
if(ds1[i] != inf)
tmp.push_back(p1[i].i);
for (int i = 0; i < (n - 1); i++)
if(ds2[i] != inf)
tmp.push_back(p2[i].i);
sort(all(tmp));
tmp.erase(unique(all(tmp)), tmp.end());
vector<bool> cool(m);
for (int j : tmp) {
cool[j] = true;
int h = -1;
//cout << ed[j].i << endl;
for (int k = 0; k < g[ed[j].u].size(); k++) {
if (g[ed[j].u][k].i == ed[j].i) {
h = k;
break;
}
}
g[ed[j].u].erase(g[ed[j].u].begin() + h);
g[ed[j].v].push_back(Edge(ed[j].i, ed[j].v, ed[j].u, ed[j].c, ed[j].d));
djikstra(0, d1);
djikstra(n - 1, d2);
if (d1[n - 1] != inf && d2[0] != inf)
ans = min(ans, d1[n - 1] + d2[0] + ed[j].d);
g[ed[j].u].push_back(ed[j]);
g[ed[j].v].pop_back();
}
for (int i = 0; i < m; i++) {
if (cool[i]) continue;
if (jopa[0][ed[i].v] == inf || jopa[ed[i].u][n - 1] == inf) continue;
ans = min(ans, jopa[0][ed[i].v]] + ed[i].c + jopa[ed[i].u][n - 1] + ed[i].d);
}
if (ans == inf) cout << -1 << endl;
else cout << ans << endl;
return;
}