제출 #535759

#제출 시각아이디문제언어결과실행 시간메모리
535759abc864197532Olympic Bus (JOI20_ho_t4)C++17
0 / 100
753 ms3876 KiB
#include <bits/stdc++.h> using namespace std; #define lli long long int #define mp make_pair #define eb emplace_back #define pb push_back #define pii pair<int,int> #define X first #define Y second #define all(x) x.begin(), x.end() void abc() {cout << endl;} template <typename T, typename ...U> void abc(T i, U ...j) { cout << i << ' ', abc(j...); } template <typename T> void printv(T l, T r) { for (; l != r; ++l) cout << *l << " \n"[l + 1 == r]; } #ifdef Doludu #define test(x...) abc("[" + string(#x) + "]", x) #define owo freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout) #else #define test(x...) void(0) #define owo ios::sync_with_stdio(false), cin.tie(0) #endif const int N = 205, M = 500001; array <int, 4> E[M]; lli dis1[2][2][N][N]; // dis[j][k] -> from s or t to k, forbid j vector <int> adj[N][2]; int n; void build1(int ty, int s, int forbid) { for (int t : {0, 1}) { for (int i = 0; i < n; ++i) { dis1[ty][t][forbid][i] = 1ll << 60; } dis1[ty][t][forbid][s] = 0; if (s == forbid) continue; priority_queue <pair <lli, int>, vector <pair <lli, int>>, greater <pair <lli, int>>> pq; pq.emplace(0, s); while (!pq.empty()) { lli d; int v; tie(d, v) = pq.top(); pq.pop(); if (d < dis1[ty][t][forbid][v]) continue; for (int id : adj[v][t]) { int u = E[id][0] ^ E[id][1] ^ v; if (u == forbid) continue; if (dis1[ty][t][forbid][u] > d + E[id][2]) dis1[ty][t][forbid][u] = d + E[id][2], pq.emplace(dis1[ty][t][forbid][u], u); } } } } lli dis2[2][N][N]; // from s to t, avoid edge (i, j) void build_special(int i, int j, int s, int t, int ty) { // ignore edge (i, j), run shortest path vector <lli> dis(n, 1ll << 60); dis[s] = 0; priority_queue <pair <lli, int>, vector <pair <lli, int>>, greater <pair <lli, int>>> pq; pq.emplace(0, s); while (!pq.empty()) { lli d; int v; tie(d, v) = pq.top(); pq.pop(); if (d < dis[v]) continue; for (int id : adj[v][0]) { int u = E[id][0] ^ E[id][1] ^ v; if (i == v && j == u) continue; if (dis[u] > d + E[id][2]) dis[u] = d + E[id][2], pq.emplace(dis[u], u); } } dis2[ty][i][j] = dis[t]; } lli ans = 0; void build2(int s, int t, int ty) { vector <lli> dis(n, 1ll << 60); vector <int> rt(n, -1); dis[s] = 0; priority_queue <pair <lli, int>, vector <pair <lli, int>>, greater <pair <lli, int>>> pq; pq.emplace(0, s); while (!pq.empty()) { lli d; int v; tie(d, v) = pq.top(); pq.pop(); if (d < dis[v]) continue; for (int id : adj[v][0]) { int u = E[id][0] ^ E[id][1] ^ v; if (dis[u] > d + E[id][2]) dis[u] = d + E[id][2], rt[u] = v, pq.emplace(dis[u], u); } } ans += dis[t]; vector <vector <bool>> in_path(n, vector <bool> (n, false)); if (dis[t] != 1ll << 60) { int now = t; while (now != s) { in_path[rt[now]][now] = true; now = rt[now]; } } for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) { if (in_path[i][j]) build_special(i, j, s, t, ty); else dis2[ty][i][j] = dis[t]; } } int main () { owo; int m; cin >> n >> m; int s = 0, t = n - 1; for (int i = 0, u, v, c, d; i < m; ++i) { cin >> u >> v >> c >> d, --u, --v; E[i] = {u, v, c, d}; adj[u][0].pb(i); adj[v][1].pb(i); } for (int i = 0; i < n; ++i) { build1(0, s, i); build1(1, t, i); } build2(s, t, 0), build2(t, s, 1); for (int i = 0; i < m; ++i) { int u = E[i][0], v = E[i][1]; lli rev = E[i][3]; lli st = min(dis1[0][0][u][v] + E[i][2] + dis1[1][1][v][u], dis2[0][u][v]); lli ts = min(dis1[1][0][u][v] + E[i][2] + dis1[0][1][v][u], dis2[1][u][v]); ans = min(ans, rev + st + ts); } if (ans >= 1ll << 40) ans = -1; cout << ans << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...