제출 #1167654

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1167654		kunzaZa183	Olympic Bus (JOI20_ho_t4)	C++20	11 / 100	73 ms	5452 KiB

ho_t4

#include <bits/stdc++.h>
using namespace std;
#define int long long
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, INT_MAX));

  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);
  }

  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, int a, int b) {
    priority_queue<pair<int, int>, vector<pair<int, int>>,
                   greater<pair<int, int>>>
        pqpii;
    pqpii.emplace(a, b);
    while (!pqpii.empty()) {
      pair<int, int> cur = pqpii.top();
      pqpii.pop();

      if (visited[cur.second] != INT_MAX) continue;

      visited[cur.second] = cur.first;

      for (auto a : adj[cur.second])
        pqpii.emplace(a.second + cur.first, a.first);
    }
  };

  // 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++) {
    vector<int> c1(floyd[0]), c2(floyd[n - 1]);

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

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

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

    // cout << i << " " << c1[n - 1] << " " << c2[0] << " " << elist[i][3] <<
    // "\n";

    minans = min(minans, c1[n - 1] + c2[0] + elist[i][3]);
  }

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

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