Submission #1311563

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311563		mio	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	174 ms	16300 KiB

commuter_pass

// #include <dbg.h>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
using ull = unsigned long long;
template <typename T> using vstack = stack<T, vector<T>>;

struct Edge2 {
  uint a, b;
};
struct Edge {
  uint b;
  ull c;
};
auto djikstra(vector<ull> &dst, uint u, const auto &edges) {
  vstack<pair<ull, uint>> st;
  dst[u] = 0;
  st.push({0, u});
  while (!st.empty()) {
    auto [d, v] = st.top();
    st.pop();
    dst[v] = d;
    for (Edge edge : edges[v]) {
      if (dst[edge.b] > d + edge.c) {
        dst[edge.b] = d + edge.c;
        st.push({dst[edge.b], d + edge.c});
      }
    }
  }
}

int main() {
  uint n, m;
  cin >> n >> m;
  uint s, t;
  cin >> s >> t;
  s--;
  t--;
  uint u, v;
  cin >> u >> v;
  u--;
  v--;
  vector<vector<Edge>> edges(n);
  for (uint i = 0; i < m; i++) {
    uint a, b;
    ull c;
    cin >> a >> b >> c;
    a--;
    b--;
    edges[a].push_back({b, c});
    edges[b].push_back({a, c});
  }
  vector<bool> special(n, false);
  vector<uint> order;
  order.reserve(n);
  // Djikstra
  vector<vector<uint>> prev(n);
  vector<ull> dst(n, -1ull);
  vstack<pair<ull, uint>> st;
  dst[s] = 0;
  st.push({0, s});
  while (!st.empty()) {
    auto [d, v] = st.top();
    st.pop();
    order.push_back(v);
    dst[v] = d;
    for (Edge edge : edges[v]) {
      if (dst[edge.b] > d + edge.c) {
        dst[edge.b] = d + edge.c;
        st.push({dst[edge.b], d + edge.c});
        prev[edge.b].assign(1, v);
      } else if (dst[edge.b] == d + edge.c) {
        prev[edge.b].push_back(v);
      }
    }
  }
  vstack<uint> to_v;
  to_v.push(t);
  while (!to_v.empty()) {
    uint v = to_v.top();
    to_v.pop();
    special[v] = true;
    for (uint p : prev[v]) {
      to_v.push(p);
    }
  }
  vector<ull> dst_u(n, -1ull);
  djikstra(dst_u, u, edges);
  vector<ull> dst_v(n, -1ull);
  djikstra(dst_v, v, edges);
  ull best_dst = -1ull;
  vector<ull> disc_dst;
  for (bool do_s : {false, true}) {
    if (do_s) {
      swap(dst_u, dst_v);
      swap(u, v);
    }
    disc_dst.assign(n, -1ull);
    for (uint v : order) {
      disc_dst[v] = dst_u[v];
      for (uint p : prev[v]) {
        disc_dst[v] = min(disc_dst[v], disc_dst[p]);
      }
      best_dst = min(best_dst, disc_dst[v] + dst_v[v]);
    }
  }
  cout << best_dst << endl;
}

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