Submission #297186

#	Time	Username	Problem	Language	Result	Execution time	Memory
297186		Bruteforceman	Olympic Bus (JOI20_ho_t4)	C++11	5 / 100	1074 ms	4344 KiB

ho_t4

#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 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 63