Submission #1214196

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214196		kunzaZa183	Olympic Bus (JOI20_ho_t4)	C++20	100 / 100	947 ms	7832 KiB

ho_t4

#include <algorithm>
#include <climits>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

const int bign = 1e9;
signed main() {
  cin.tie(0)->sync_with_stdio(0);

  int n, m;
  cin >> n >> m;

  vector<vector<int>> elist;
  elist.push_back({0, 0, 0, 0});

  vector<vector<int>> floyd(n, vector<int>(n, bign));

  for (int i = 0; i < n; i++) {
    floyd[i][i] = 0;
  }

  vector<vector<pair<int, int>>> adj(n, vector<pair<int, int>>());

  for (int i = 0; i < m; i++) {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    a--, b--;
    elist.push_back({a, b, c, d});
    floyd[a][b] = min(floyd[a][b], c);
    adj[a].emplace_back(b, c);
  }

  sort(elist.begin(), elist.end());

  for (int times = 0; times < 6; times++)
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        for (int k = 0; k < n; k++) {
          floyd[i][j] = min(floyd[i][j], floyd[i][k] + floyd[k][j]);
        }
      }
    }

  auto dijkstra = [&](vector<int>& visited, vector<int>& bef, int len, int in,
                      int from) {
    priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>>
        pqpii;
    pqpii.push({len, in, from});
    while (!pqpii.empty()) {
      vector<int> cur = pqpii.top();
      pqpii.pop();

      if (visited[cur[1]] <= cur[0]) continue;

      visited[cur[1]] = cur[0];
      bef[cur[1]] = cur[2];

      for (auto a : adj[cur[1]])
        pqpii.push({a.second + cur[0], a.first, cur[1]});
    }
  };

  auto dijkstra2 = [&](vector<int>& visited, int len, int in) {
    priority_queue<pair<int, int>, vector<pair<int, int>>,
                   greater<pair<int, int>>>
        pqpii;
    pqpii.emplace(len, in);
    while (!pqpii.empty()) {
      pair<int, int> cur = pqpii.top();
      pqpii.pop();

      if (visited[cur.second] <= cur.first) continue;

      visited[cur.second] = cur.first;

      for (auto a : adj[cur.second])
        if (visited[a.first] == bign) {
          pqpii.push({a.second + cur.first, a.first});
        }
    }
  };

  vector<int> visited(n, bign), bef1(n, -1), bef2(n, -1);

  dijkstra(visited, bef1, 0, 0, -1);
  vector<int> visited2(n, bign);
  dijkstra(visited2, bef2, 0, n - 1, -1);

  // if (visited[n - 1] == INT_MAX && visited2[0] == INT_MAX) {
  //     cout << "-1\n";
  //     return 0;
  // }

  vector<int> partof(m + 1);

  if (visited[n - 1] != bign) {
    vector<int> path1;
    int cur = n - 1;
    while (cur != -1) {
      path1.push_back(cur);
      cur = bef1[cur];
    }

    reverse(path1.begin(), path1.end());

    for (int i = 0; i < path1.size() - 1; i++) {
      int it = lower_bound(elist.begin(), elist.end(),
                           vector<int>({path1[i], path1[i + 1], 0, 0})) -
               elist.begin();
      partof[it] = 1;
    }
  }

  if (visited2[n - 1] != bign) {
    vector<int> path2;

    int cur = 0;
    while (cur != -1) {
      path2.push_back(cur);
      cur = bef2[cur];
    }

    reverse(path2.begin(), path2.end());

    for (int i = 0; i < path2.size() - 1; i++) {
      int it = lower_bound(elist.begin(), elist.end(),
                           vector<int>({path2[i], path2[i + 1], 0, 0})) -
               elist.begin();
      partof[it] = 1;
    }
  }

  // for (int i = 0; i < n; i++) {
  //   for (int j = 0; j < n; j++) {
  //     cout << floyd[i][j] << " ";
  //   }
  //   cout << "\n";
  // }

  int minans = INT_MAX;
  for (int i = 0; i <= m; i++) {
    if (partof[i]) {
      int u = elist[i][0], v = elist[i][1], cst = elist[i][2],
          price = elist[i][3];
      adj[u].erase(find(adj[u].begin(), adj[u].end(), make_pair(v, cst)));

      adj[v].emplace_back(u, cst);

      visited = vector<int>(n, bign);
      dijkstra2(visited, 0, 0);

      if (visited[n - 1] == bign) {
        adj[v].erase(find(adj[v].begin(), adj[v].end(), make_pair(u, cst)));

        adj[u].emplace_back(v, cst);
        continue;
      }
      price += visited[n - 1];

      visited = vector<int>(n, bign);
      dijkstra2(visited, 0, n - 1);

      if (visited[0] == bign) {
        adj[v].erase(find(adj[v].begin(), adj[v].end(), make_pair(u, cst)));

        adj[u].emplace_back(v, cst);
        continue;
      }
      price += visited[0];

      minans = min(minans, price);

      adj[v].erase(find(adj[v].begin(), adj[v].end(), make_pair(u, cst)));

      adj[u].emplace_back(v, cst);
    } else {
      vector<int> c1(floyd[0]), c2(floyd[n - 1]);

      int u = elist[i][1], v = elist[i][0], cst = elist[i][2];

      if (c1[u] != bign) c1[v] = min(c1[v], c1[u] + cst);
      if (c2[u] != bign) c2[v] = min(c2[v], c2[u] + cst);

      for (int j = 0; j < n; j++) {
        if (floyd[v][j] != bign && c1[v] != bign)
          c1[j] = min(c1[j], c1[v] + floyd[v][j]);
        if (floyd[v][j] != bign && c2[v] != bign)
          c2[j] = min(c2[j], c2[v] + floyd[v][j]);
      }

      // cout << i << " " << c1[n - 1] << " " << c2[0] << " " << elist[i][3] <<
      // "\n";
      if (c1[n - 1] != bign && c2[0] != bign)
        minans = min(minans, c1[n - 1] + c2[0] + elist[i][3]);
    }
  }

  if (minans == INT_MAX) {
    cout << "-1\n";
  } else
    cout << minans << "\n";
}

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