oj.uz

Submission #297191

# Submission time Handle Problem Language Result Execution time Memory
297191 2020-09-11T10:45:18 Z Bruteforceman Olympic Bus (JOI20_ho_t4) C++11
5 / 100
 1000 ms 4216 KB 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 205;
const int maxm = 5e4 + 10;
const long long inf = 1e15;
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);
  vector <bool> done (n, false);
  d[src] = 0;
  while(true) {
    int x = -1;
    for(int i = 0; i < n; i++) {
      if(done[i]) continue;
      if(x == -1 || d[x] > d[i]) {
        x = i;
      }
    }
    if(x == -1) break;
    done[x] = true;
    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]) {
        d[y] = d[x] + w[e];
      }
    }
  }
  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 169 ms 384 KB Output is correct
2 Correct 86 ms 504 KB Output is correct
3 Correct 229 ms 504 KB Output is correct
4 Correct 241 ms 504 KB Output is correct
5 Correct 7 ms 384 KB Output is correct
6 Correct 49 ms 384 KB Output is correct
7 Correct 0 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 112 ms 384 KB Output is correct
11 Correct 152 ms 384 KB Output is correct
12 Correct 139 ms 512 KB Output is correct
13 Correct 124 ms 504 KB Output is correct
14 Correct 194 ms 504 KB Output is correct
15 Correct 198 ms 504 KB Output is correct
16 Correct 196 ms 384 KB Output is correct

Subtask #2
0 / 11.0

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

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 384 KB Output is correct
2 Correct 92 ms 384 KB Output is correct
3 Execution timed out 1051 ms 3396 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 384 KB Output is correct
2 Correct 86 ms 504 KB Output is correct
3 Correct 229 ms 504 KB Output is correct
4 Correct 241 ms 504 KB Output is correct
5 Correct 7 ms 384 KB Output is correct
6 Correct 49 ms 384 KB Output is correct
7 Correct 0 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 112 ms 384 KB Output is correct
11 Correct 152 ms 384 KB Output is correct
12 Correct 139 ms 512 KB Output is correct
13 Correct 124 ms 504 KB Output is correct
14 Correct 194 ms 504 KB Output is correct
15 Correct 198 ms 504 KB Output is correct
16 Correct 196 ms 384 KB Output is correct
17 Execution timed out 1048 ms 4216 KB Time limit exceeded
18 Halted 0 ms 0 KB -