Submission #1188005

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188005		kilikuma	Commuter Pass (JOI18_commuter_pass)	C++20	40 / 100	222 ms	29008 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int INF = (int) (1e18);

signed main() {

  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);

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

  int s, t, u, v; cin >> s >> t >> u >> v;

  vector<pair<int, int>> adja[n + 1];

  vector<int> distanceCur(n + 1, 0);

  vector<int> distanceS(n + 1, 0);
  vector<int> distanceT(n + 1, 0);
  vector<int> distanceU(n + 1, 0);
  vector<int> distanceV(n + 1, 0);

  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

  for (int i = 1; i <= m; i ++) {
    int dest, dep, pds; cin >> dest >> dep >> pds;
    adja[dest].push_back({dep, pds});
    adja[dep].push_back({dest, pds});
  }

  // destination, puis poids

  distanceCur.assign(n + 1, INF);
  distanceCur[s] = 0;
  pq.push({0, s});
  while (! pq.empty()) {
    auto som = pq.top();
    pq.pop();
    if (som.first != distanceCur[som.second])
      continue;
    for (auto voisin : adja[som.second]) {
      if (distanceCur[voisin.first] > voisin.second + som.first) {
        distanceCur[voisin.first] = voisin.second + som.first;
        pq.push({distanceCur[voisin.first], voisin.first});
      }
    }
  }
  distanceS = distanceCur;

  distanceCur.assign(n + 1, INF);
  distanceCur[t] = 0;
  pq.push({0, t});
  while (! pq.empty()) {
    auto som = pq.top();
    pq.pop();
    if (som.first != distanceCur[som.second])
      continue;
    for (auto voisin : adja[som.second]) {
      if (distanceCur[voisin.first] > voisin.second + som.first) {
        distanceCur[voisin.first] = voisin.second + som.first;
        pq.push({distanceCur[voisin.first], voisin.first});
      }
    }
  }
  distanceT = distanceCur;

  distanceCur.assign(n + 1, INF);
  distanceCur[u] = 0;
  pq.push({0, u});
  while (! pq.empty()) {
    auto som = pq.top();
    pq.pop();
    if (som.first != distanceCur[som.second])
      continue;
    for (auto voisin : adja[som.second]) {
      if (distanceCur[voisin.first] > voisin.second + som.first) {
        distanceCur[voisin.first] = voisin.second + som.first;
        pq.push({distanceCur[voisin.first], voisin.first});
      }
    }
  }
  distanceU = distanceCur;

  distanceCur.assign(n + 1, INF);
  distanceCur[v] = 0;
  pq.push({0, v});
  while (! pq.empty()) {
    auto som = pq.top();
    pq.pop();
    if (som.first != distanceCur[som.second])
      continue;
    for (auto voisin : adja[som.second]) {
      if (distanceCur[voisin.first] > voisin.second + som.first) {
        distanceCur[voisin.first] = voisin.second + som.first;
        pq.push({distanceCur[voisin.first], voisin.first});
      }
    }
  }
  distanceV = distanceCur;

  int ans = distanceU[v];

  vector<int> distanceSU(n + 1, INF);
  vector<int> distanceSV(n + 1, INF);
  vector<int> distanceTU(n + 1, INF);
  vector<int> distanceTV(n + 1, INF);

  for (int i = 1; i <= n; i ++) {
    distanceSU[i] = distanceU[i];
    distanceTU[i] = distanceU[i];
    distanceSV[i] = distanceV[i];
    distanceTV[i] = distanceV[i];
  }

  vector<pair<int, int>> SU;

  for (int i = 0; i < n; i ++) {
    SU.push_back({distanceS[i], i});
  }
  sort(SU.begin(), SU.end());

  for (int i = 1; i < n; i ++) {
    int node = SU[i].second;
    for (auto voi : adja[node]) {
      if (distanceS[voi.first] + voi.second == distanceS[node])
        distanceSU[node] = min(distanceSU[node], distanceSU[voi.first]);
    }
  }

  vector<pair<int, int>> SV;

  for (int i = 0; i < n; i ++) {
    SV.push_back({distanceS[i], i});
  }
  sort(SV.begin(), SV.end());

  for (int i = 1; i < n; i ++) {
    int node = SV[i].second;
    for (auto voi : adja[node]) {
      if (distanceS[voi.first] + voi.second == distanceS[node])
        distanceSV[node] = min(distanceSV[node], distanceSV[voi.first]);
    }
  }

  vector<pair<int, int>> TU;

  for (int i = 0; i < n; i ++) {
    TU.push_back({distanceT[i], i});
  }
  sort(TU.begin(), TU.end());

  for (int i = 1; i < n; i ++) {
    int node = TU[i].second;
    for (auto voi : adja[node]) {
      if (distanceT[voi.first] + voi.second == distanceT[node])
        distanceTU[node] = min(distanceTU[node], distanceTU[voi.first]);
    }
  }

  vector<pair<int, int>> TV;

  for (int i = 0; i < n; i ++) {
    TV.push_back({distanceT[i], i});
  }
  sort(TV.begin(), TV.end());

  for (int i = 1; i < n; i ++) {
    int node = TV[i].second;
    for (auto voi : adja[node]) {
      if (distanceT[voi.first] + voi.second == distanceT[node])
        distanceTV[node] = min(distanceTV[node], distanceTV[voi.first]);
    }
  }

  for (int w = 1; w <= n; w ++) {
    if (distanceS[w] + distanceT[w] == distanceS[t]) {
      ans = min(ans, distanceSU[w] + distanceTV[w]);
      ans = min(ans, distanceSV[w] + distanceTU[w]);
    }
  }

  cout << ans << '\n'; 

}

• Subtask 1: 16 / 16
• Subtask 2: 0 / 15
• Subtask 3: 24 / 24
• Subtask 4: 0 / 45