oj.uz

답안 #244925

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
244925 2020-07-05T09:33:31 Z rama_pang Olympic Bus (JOI20_ho_t4) C++14
5 / 100
 1000 ms 2796 KB 
#include <bits/stdc++.h>
using namespace std;

using lint = long long;
const int MAXN = 205;
const int MAXM = 50005;

int N, M;
vector<int> adj[MAXN];
vector<int> radj[MAXN];
vector<array<int, 4>> edge;

int par[5][MAXN];
lint dist[5][MAXN];
int sptree[5][MAXM];

lint Dijkstra(int s, int k, vector<int> a[MAXN], int block = -1, int ru = -1, int rv = -1, int rc = -1, int target = -1) {
  for (int i = 0; i < MAXN; i++) {
    dist[k][i] = 1e18;
  }

  priority_queue<pair<lint, int>, vector<pair<lint, int>>, greater<pair<lint, int>>> pq;
  pq.emplace(0, s);
  auto dt = dist[k];
  auto pr = par[k];
  dt[s] = 0;
  pr[s] = -1;
  while (!pq.empty()) {
    int u = pq.top().second;
    lint d = pq.top().first;
    pq.pop();
    if (dt[u] != d) {
      continue;
    }
    if (u == target) {
      return d;
    }
    if (pr[u] != -1) {
      sptree[k][pr[u]] = 1;
    }
    for (auto e : a[u]) if (e != block) {
      int v = edge[e][0] ^ edge[e][1] ^ u;
      if (dt[v] > dt[u] + edge[e][2]) {
        dt[v] = dt[u] + edge[e][2];
        pr[v] = e;
        pq.emplace(dt[v], v);
      }
    }
    if (u == ru) {
      int v = rv;
      if (dt[v] > dt[u] + rc) {
        dt[v] = dt[u] + rc;
        pr[v] = block;
        pq.emplace(dt[v], v);
      } 
    }
  }
  return 1e18;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  cin >> N >> M;
  for (int i = 0; i < M; i++) {
    int u, v, c, d;
    cin >> u >> v >> c >> d;
    edge.push_back({u, v, c, d});
    adj[u].emplace_back(i);
    radj[v].emplace_back(i);
  }

  Dijkstra(1, 0, adj); // 1 to N
  Dijkstra(N, 1, adj); // N to 1
  Dijkstra(1, 2, radj); // 1 to N, reverse
  Dijkstra(N, 3, radj); // N to 1, reverse
  lint ans = dist[0][N] + dist[1][1];
  for (int i = 0; i < M; i++) {
    int u, v, c, d;
    u = edge[i][0], v = edge[i][1], c = edge[i][2], d = edge[i][3];
    // if (sptree[0][i] == 0 && sptree[1][i] == 0) {
      // ans = min(ans, d + min(dist[0][N], dist[0][v] + c + dist[2][u]) + 
                        //  min(dist[1][1], dist[1][v] + c + dist[3][u]));
    // } else {
      ans = min(ans, d + Dijkstra(1, 4, adj, i, v, u, c, N) + Dijkstra(N, 4, adj, i, v, u, c, 1));
    // }
  }
  if (ans > 1e17) {
    ans = -1;
  }
  cout << ans << "\n";
  return 0;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 37 ms 512 KB Output is correct
4 Correct 47 ms 384 KB Output is correct
5 Correct 17 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 7 ms 384 KB Output is correct
10 Correct 86 ms 632 KB Output is correct
11 Correct 81 ms 384 KB Output is correct
12 Correct 85 ms 384 KB Output is correct
13 Correct 32 ms 384 KB Output is correct
14 Correct 37 ms 384 KB Output is correct
15 Correct 29 ms 384 KB Output is correct
16 Correct 45 ms 384 KB Output is correct

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1097 ms 2796 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Execution timed out 1083 ms 2284 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 37 ms 512 KB Output is correct
4 Correct 47 ms 384 KB Output is correct
5 Correct 17 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 7 ms 384 KB Output is correct
10 Correct 86 ms 632 KB Output is correct
11 Correct 81 ms 384 KB Output is correct
12 Correct 85 ms 384 KB Output is correct
13 Correct 32 ms 384 KB Output is correct
14 Correct 37 ms 384 KB Output is correct
15 Correct 29 ms 384 KB Output is correct
16 Correct 45 ms 384 KB Output is correct
17 Execution timed out 1097 ms 2796 KB Time limit exceeded
18 Halted 0 ms 0 KB -