Submission #1159824

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159824		fryingduc	Olympic Bus (JOI20_ho_t4)	C++20	0 / 100	96 ms	8632 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];
bool opt[M];
long long d[maxn][2][maxn][2];
map<pair<int, int>, int> mp;

void dijkstra(int src) {
  memset(d, 0x3f, sizeof(d));
  d[src][0][0][0] = 0;
  using T = tuple<long long, int, bool, int, bool>;
  priority_queue<T, vector<T>, greater<T>> pq;
  pq.emplace(0, src, 0, 0, 0);
  while (!pq.empty()) {
    auto [dist, u, round, rv, best] = pq.top();
    pq.pop();
//    debug(u, round, rv, dist);
    if (dist > d[u][round][rv][best]) continue;
    for (auto [v, id] : g[u]) {
      int nxt_round = round | (v == n);
      if (rv == v) {
        if (!(best and opt[id])) {
          if (d[v][nxt_round][n + 1][0] > dist + ew[id]) {
            d[v][nxt_round][n + 1][0] = dist + ew[id];
            pq.emplace(d[v][nxt_round][n + 1][0], v, nxt_round, n + 1, 0);
          }
        }
      } else {
        int xx = (!rv ? 0 : n + 1);
        if (d[v][nxt_round][xx][0] > dist + ew[id]) {
          d[v][nxt_round][xx][0] = dist + ew[id];
          pq.emplace(d[v][nxt_round][xx][0], v, nxt_round, xx, 0);
        }
      }
    }
    if (!rv) {
      for (auto [v, id] : rev_g[u]) {
        int nxt_round = round | (v == n);
        if (d[v][nxt_round][u][opt[id]] > dist + ew[id] + ed[id]) {
          d[v][nxt_round][u][opt[id]] = dist + ew[id] + ed[id];
          pq.emplace(d[v][nxt_round][u][1], v, nxt_round, u, opt[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;
    if (!mp.count(make_pair(u, v))) {
      mp[make_pair(u, v)] = i;
    } else if (ew[mp[make_pair(u, v)]] > ew[i]) {
      mp[make_pair(u, v)] = i;
    }
  }
  for (auto [u, id] : mp) {
    opt[id] = 1;
  }
  dijkstra(1);
  long long res = 1e18;
  for (int i = 0; i <= n + 1; ++i) {
    for (int j = 0; j < 2; ++j) {
      res = min(res, d[1][1][i][j]);
    }
  }
  cout << (res > 1e17 ? -1 : res);
}

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

  solve();

  return 0;
}

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