oj.uz

Submission #297186

# Submission time Handle Problem Language Result Execution time Memory
297186 2020-09-11T10:40:10 Z Bruteforceman Olympic Bus (JOI20_ho_t4) C++11
5 / 100
 1000 ms 4344 KB 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 205;
const int maxm = 5e4 + 10;
const long long inf = 1e15;
struct vertex {
  int node;
  long long dist;
  vertex (int node, long long dist) : node(node), dist(dist) {}
  vertex () {}
  bool operator < (vertex v) const {
    return dist > v.dist;
  }
};
bool del[maxm];
int l[maxm], r[maxm], w[maxm], c[maxm];
int n, m;
vector <int> g[maxn];
bool imp[maxm];

vector <long long> shortest_path(int src, bool rev = false, bool mark = false) {
  vector <long long> d (n, inf);
  priority_queue <vertex> Q;
  Q.emplace(src, 0);
  d[src] = 0;
  while(not Q.empty()) {
    auto x = Q.top();
    Q.pop();
    if(x.dist != d[x.node]) continue;
    for(int e : g[x.node]) {
      if(del[e]) continue;
      if(rev && l[e] == x.node) continue;
      if(!rev && r[e] == x.node) continue;
      int y = l[e] ^ r[e] ^ x.node;
      if(d[y] > x.dist + w[e]) {
        d[y] = x.dist + w[e];
        Q.emplace(y, d[y]);
      }
    }
  }
  if(mark) {
    vector <int> par (n, -1);
    for(int x = 0; x < n; x++) {
      for(int e : g[x]) {
        if(del[e]) continue;
        if(rev && l[e] == x) continue;
        if(!rev && r[e] == x) continue;
        int y = l[e] ^ r[e] ^ x;
        if(d[y] == d[x] + w[e]) {
          par[y] = e;
        }
      }
    }
    for(int i = 0; i < n; i++) if(par[i] != -1) imp[par[i]] = true;
  }
  return d;
}
int main() {
  cin >> n >> m;
  for(int i = 0; i < m; i++) {
    cin >> l[i] >> r[i] >> w[i] >> c[i];
    l[i] -= 1;
    r[i] -= 1;
    g[l[i]].push_back(i);
    g[r[i]].push_back(i);
  }
  
  auto fromSrc = shortest_path(0, false, true);
  auto fromDes = shortest_path(n - 1, false, true);
  auto toSrc = shortest_path(0, true, true);
  auto toDes = shortest_path(n - 1, true, true);

  vector <long long> srcPath (m, inf), desPath(m, inf);
  vector <long long> leftSrc (m, inf), srcRight (m, inf);
  vector <long long> leftDes (m, inf), desRight (m, inf);
  for(int i = 0; i < m; i++) {
    if(imp[i]) {
      del[i] = true;
      auto u = shortest_path(0);
      auto v = shortest_path(n - 1);
      srcRight[i] = u[r[i]];
      desRight[i] = v[r[i]];
      srcPath[i] = u[n - 1];
      desPath[i] = v[0];
      u = shortest_path(0, true);
      v = shortest_path(n - 1, true);
      leftSrc[i] = u[l[i]];
      leftDes[i] = v[l[i]];
      del[i] = false;
    } else {
      srcRight[i] = fromSrc[r[i]];
      desRight[i] = fromDes[r[i]];
      leftSrc[i] = toSrc[l[i]];
      leftDes[i] = toDes[l[i]];
      srcPath[i] = fromSrc[n - 1];
      desPath[i] = fromDes[0];
    }
  }
  long long ans = fromSrc[n - 1] + fromDes[0];
  for(int i = 0; i < m; i++) {
    long long res = c[i];
    res += min(srcRight[i] + w[i] + leftDes[i], srcPath[i]);
    res += min(desRight[i] + w[i] + leftSrc[i], desPath[i]);
    ans = min(ans, res);
  }
  if(ans >= inf) ans = -1;
  cout << ans << endl;
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 66 ms 384 KB Output is correct
4 Correct 71 ms 512 KB Output is correct
5 Correct 8 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 46 ms 512 KB Output is correct
11 Correct 57 ms 512 KB Output is correct
12 Correct 53 ms 512 KB Output is correct
13 Correct 15 ms 416 KB Output is correct
14 Correct 42 ms 512 KB Output is correct
15 Correct 40 ms 512 KB Output is correct
16 Correct 40 ms 512 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1074 ms 4344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Execution timed out 1062 ms 3576 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 66 ms 384 KB Output is correct
4 Correct 71 ms 512 KB Output is correct
5 Correct 8 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 46 ms 512 KB Output is correct
11 Correct 57 ms 512 KB Output is correct
12 Correct 53 ms 512 KB Output is correct
13 Correct 15 ms 416 KB Output is correct
14 Correct 42 ms 512 KB Output is correct
15 Correct 40 ms 512 KB Output is correct
16 Correct 40 ms 512 KB Output is correct
17 Execution timed out 1074 ms 4344 KB Time limit exceeded
18 Halted 0 ms 0 KB -