oj.uz

Submission #1036842

# Submission time Handle Problem Language Result Execution time Memory
1036842 2024-07-27T17:54:48 Z juicy Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 90 ms 3812 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
 
const int N = 205, M = 5e4 + 5;
const int inf = 1e9;
 
int n, m;
int pr[N], w[M], d[2][N];
array<int, 2> f[N];
bool spec[M];
vector<array<int, 2>> g[N], rg[N];
array<int, 3> edges[M];
 
void dijkstra(int s, int *d) {
  using T = array<int, 2>;
  priority_queue<T, vector<T>, greater<T>> pq;
  fill(d + 1, d + n + 1, inf);
  fill(pr + 1, pr + n + 1, 0);
  pq.push({d[s] = 0, s});
  while (pq.size()) {
    auto [c, u] = pq.top(); pq.pop();
    if (c != d[u]) {
      continue;
    }
    for (auto [v, id] : g[u]) {
      if (d[v] > d[u] + w[id]) {
        pr[v] = id;
        pq.push({d[v] = d[u] + w[id], v});
      }
    }
  }
}

void mark() {
  for (int i = 1; i <= n; ++i) {
    spec[pr[i]] = 1;
  }
}
 
void solve(int src) {
  fill(f + 1, f + n + 1, array<int, 2>{inf, inf});
  using T = array<int, 3>;
  priority_queue<T, vector<T>, greater<T>> pq;
  pq.push({f[src][0] = 0, src, 0});
  while (pq.size()) {
    auto [c, u, type] = pq.top(); pq.pop();
    if (f[u][type] != c) {
      continue;
    }
    for (auto [v, id] : g[u]) {
      if (f[v][type] > c + w[id]) {
        pq.push({f[v][type] = c + w[id], v, type});
      }
    }
    if (!type) {
      for (auto [v, id] : rg[u]) {
        if (!spec[id] && f[v][1] > c + w[id] + edges[id][2]) {
          pq.push({f[v][1] = c + w[id] + edges[id][2], v, 1});
        }
      }
    } 
  }
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);
 
  cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    int u, v, c; cin >> u >> v >> w[i] >> c;
    edges[i] = {u, v, c};
    g[u].push_back({v, i});
    rg[v].push_back({u, i});
  }
  dijkstra(1, d[0]);
  mark();
  dijkstra(n, d[1]);
  mark();
  auto del = [&](int u, array<int, 2> x) {
    for (auto &v : g[u]) {
      if (v == x) {
        swap(v, g[u].back());
        g[u].pop_back();
        break;
      }
    }
  };
  auto add = [&](int u, array<int, 2> x) {
    g[u].push_back(x);
  };
  int res = 2 * inf;
  if (d[0][n] != inf && d[1][1] != inf) {
    res = d[0][n] + d[1][1];
  }
  solve(1);
  if (d[1][1] != inf && f[n][1] != inf) {
    res = min(res, d[1][1] + f[n][1]);
  }
  solve(n);
  if (d[0][n] != inf && f[1][1] != inf) {
    res = min(res, d[0][n] + f[1][1]);
  }
  for (int i = 1; i <= m; ++i) {
    if (spec[i]) {
      auto [u, v, c] = edges[i];
      del(u, {v, i});
      add(v, {u, i});
      dijkstra(1, d[0]);
      dijkstra(n, d[1]);
      if (d[0][n] != inf && d[1][1] != inf) {
        res = min(res, d[0][n] + d[1][1] + c);
      }
      del(v, {u, i});
      add(u, {v, i});
    }
  }
  cout << (res != 2 * inf ? res : -1);
  return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 10 ms 572 KB Output is correct
4 Correct 12 ms 576 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 600 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 11 ms 348 KB Output is correct
11 Correct 14 ms 344 KB Output is correct
12 Correct 14 ms 348 KB Output is correct
13 Incorrect 3 ms 348 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 3712 KB Output is correct
2 Correct 90 ms 3648 KB Output is correct
3 Correct 83 ms 3676 KB Output is correct
4 Correct 7 ms 604 KB Output is correct
5 Correct 4 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 26 ms 3812 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 50 ms 2804 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 57 ms 3576 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 20 ms 3588 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 10 ms 572 KB Output is correct
4 Correct 12 ms 576 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 600 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 11 ms 348 KB Output is correct
11 Correct 14 ms 344 KB Output is correct
12 Correct 14 ms 348 KB Output is correct
13 Incorrect 3 ms 348 KB Output isn't correct
14 Halted 0 ms 0 KB -