Submission #1159872

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159872		fryingduc	Olympic Bus (JOI20_ho_t4)	C++20	100 / 100	511 ms	2684 KiB

ho_t4

#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 205;
const int M = 5e4 + 4;
int n, m;
int eu[M], ev[M], ew[M], ed[M];
vector<pair<int, int>> g[maxn], rev_g[maxn];
long long d[2][maxn], rev[2][maxn];
long long dd[2][maxn];
int tr[maxn];
bool opt[M];

void dijkstra(int src, long long d[], bool rv) {
  for (int i = 1; i <= n; ++i) {
    d[i] = 1e18;
    tr[i] = 0;
  }
  d[src] = 0;
  using T = pair<long long, int>;
  priority_queue<T, vector<T>, greater<T>> pq;
  pq.emplace(0, src);
  while (!pq.empty()) {
    auto [dist, u] = pq.top();
    pq.pop();
    if (dist > d[u]) continue;
    vector<pair<int, int>> &adj = (rv ? rev_g[u] : g[u]);
    for (auto [v, id] : adj) {
      if (d[v] > ew[id] + dist) {
        tr[v] = id;
        pq.emplace(d[v] = ew[id] + dist, v);
      }
    }
  }
}

void invert(int id) {
  int u = eu[id], v = ev[id];
  for (int i = 0; i < (int)g[u].size(); ++i) {
    if (g[u][i].second == id) {
      swap(g[u][i], g[u][(int)g[u].size() - 1]);
      g[u].pop_back();
      break;
    }
  }
  g[v].emplace_back(u, id);
  swap(eu[id], ev[id]);
}

void solve() {
  cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    int u, v, w, d; cin >> u >> v >> w >> d;
    g[u].emplace_back(v, i);
    rev_g[v].emplace_back(u, i);
    eu[i] = u, ev[i] = v, ew[i] = w, ed[i] = d;
  }
  dijkstra(1, d[0], 0);
  for (int i = 1; i <= n; ++i) {
    opt[tr[i]] = 1;
  }
  dijkstra(n, d[1], 0);
  for (int i = 1; i <= n; ++i) {
    opt[tr[i]] = 1;
  }
  dijkstra(1, rev[0], 1);
  dijkstra(n, rev[1], 1);
  long long res = d[0][n] + d[1][1];
  for (int i = 1; i <= m; ++i) {
    int u = eu[i], v = ev[i];
    if (!opt[i]) {
      long long x = min(d[0][n], d[0][v] + rev[1][u] + ew[i]);
      long long y = min(d[1][1], d[1][v] + rev[0][u] + ew[i]);
//      debug(i, x, y, ed[i]);
      res = min(res, ed[i] + x + y);
    } else {
      invert(i);
      dijkstra(1, dd[0], 0);
      dijkstra(n, dd[1], 0);
//      debug(i, dd[0][n], dd[1][1], ed[i]);
      res = min(res, dd[0][n] + dd[1][1] + ed[i]);
      invert(i);
    }
  }
  cout << (res > 1e17 ? -1 : res);
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 21 / 21
• Subtask 4: 63 / 63