Submission #591412

#	Time	Username	Problem	Language	Result	Execution time	Memory
591412		MilosMilutinovic	Olympic Bus (JOI20_ho_t4)	C++14	0 / 100	205 ms	3816 KiB

ho_t4

/**
 *    author:  wxhtzdy
 *    created: 07.07.2022 13:22:29
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n, m;
  cin >> n >> m;                     
  vector<int> u(m), v(m), c(m), d(m);
  vector<vector<tuple<int, int, int>>> g(n);
  const long long inf = 1e15;
  vector<vector<long long>> f(n, vector<long long>(n, inf));
  for (int i = 0; i < m; i++) {
    cin >> u[i] >> v[i] >> c[i] >> d[i];
    --u[i]; --v[i];
    g[u[i]].emplace_back(v[i], c[i], i);
    f[u[i]][v[i]] = c[i];
  }
  for (int i = 0; i < n; i++) {
    f[i][i] = 0;
  }
  for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
      }
    }
  }                        
  vector<vector<int>> ids(2);
  vector<vector<long long>> dist(2, vector<long long>(n));
  function<void(int, int, int)> FindPath = [&](int s, int t, int id) {
    fill(dist[id].begin(), dist[id].end(), inf);
    set<pair<long long, int>> st;
    vector<int> prv(n);
    dist[id][s] = 0;
    st.emplace(0, s);
    while (!st.empty()) {
      auto it = st.begin();
      int i = it->second;
      st.erase(it);
      for (auto& e : g[i]) {
        int to = get<0>(e);
        int w = get<1>(e);
        int idx = get<2>(e);
        if (dist[id][to] > dist[id][i] + w) {
          if (dist[id][to] != inf) {
            st.erase(st.find({dist[id][to], to}));
          }
          dist[id][to] = dist[id][i] + w;
          prv[to] = idx;
          st.emplace(dist[id][to], to);
        }
      }
    }
    if (dist[id][t] != inf) {
      while (t != s) {
        ids[id].push_back(prv[t]);
        t = u[prv[t]];
      }
    }            
  };
  FindPath(0, n - 1, 0);
  FindPath(n - 1, 0, 1);
  if (ids[0].empty() && ids[1].empty()) {
    cout << -1 << '\n';
    return 0;
  }
  vector<int> on(m, -1);
  for (int r = 0; r < 2; r++) {
    for (int i : ids[r]) {
      on[i] = r;      
    }
  }         
  long long ans = min(inf, f[0][n - 1] + f[n - 1][0]);
  auto Solve = [&](int id) {
    vector<vector<long long>> q(n, vector<long long>(n, inf));
    for (int i = 0; i < m; i++) {
      if (i == id) {
        q[v[i]][u[i]] = c[i] + d[i];
      } else {
        q[u[i]][v[i]] = c[i];
      }
    }
    for (int i = 0; i < n; i++) {
      q[i][i] = 0;
    }
    for (int k = 0; k < n; k++) {
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
          q[i][j] = min(q[i][j], q[i][k] + q[k][j]);
        }
      }
    }
    return q[0][n - 1] + q[n - 1][0];
  };
  for (int i = 0; i < m; i++) {
    if (on[i] != -1) {
      ans = min(ans, Solve(i));
      continue;                      
    }
    ans = min(ans, f[n - 1][0] + f[0][v[i]] + c[i] + d[i] + f[u[i]][n - 1]);
    ans = min(ans, f[n - 1][v[i]] + c[i] + d[i] + f[u[i]][0] + f[0][n - 1]);
  }
  cout << (ans == inf ? (long long) -1 : ans) << '\n';
  return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 63