Submission #615466

#	Time	Username	Problem	Language	Result	Execution time	Memory
615466		MilosMilutinovic	Olympic Bus (JOI20_ho_t4)	C++14	0 / 100	1093 ms	7792 KiB

ho_t4

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

using namespace std;

#define int long long

signed 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 = 1e16;
  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]] = min(f[u[i]][v[i]], (long long) 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]);
      }
    }
  }
  auto ng = g;         
  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 : ng[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);
        }
      }
    }
    ids[id].clear();
    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);
  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) {
    for (int i = 0; i < n; i++) {
      ng[i].clear();
    }
    swap(u[id], v[id]);
    for (int i = 0; i < m; i++) {
      ng[u[i]].emplace_back(v[i], c[i] + (i == id ? d[i] : 0), i);  
    }
    FindPath(0, n - 1, 0);
    FindPath(n - 1, 0, 1);
    swap(u[id], v[id]);
    return dist[0][n - 1] + dist[1][0];
  };
  long long nans = ans;
  for (int i = 0; i < m; i++) {
    if (true) {                         
      ans = min(ans, Solve(i));
    }
    if (on[i] == -1) {
      nans = min(nans, f[n - 1][0] + f[0][v[i]] + c[i] + d[i] + f[u[i]][n - 1]);
      nans = min(nans, f[n - 1][v[i]] + c[i] + d[i] + f[u[i]][0] + f[0][n - 1]);
    } else {
      nans = min(nans, Solve(i));
    }
  }
  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