Submission #1235754

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235754		thewizardman	Commuter Pass (JOI18_commuter_pass)	C++20	15 / 100	157 ms	27044 KiB

commuter_pass

#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <bits/stdc++.h>
using namespace std;

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// template<typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pli pair<ll, int>
#define plpll pair<ll, pll>
#define pipii pair<int, pii>
#define plpii pair<ll, pii>
#define pipll pair<int, pll>
#define lll tuple<ll, ll, ll>
#define iii tuple<int, int, int>
#define lii tuple<ll, int, int>
#define lli tuple<ll, ll, int>
#define md 1000000007LL
#define linf 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define lninf (ll)0xc0c0c0c0c0c0c0c0
#define ninf (int)0xc0c0c0c0
#define bruh ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ss << ' ' <<
#ifdef wizard
  #define usaco(x)
#else
  #define usaco(x) ifstream cin(#x ".in"); ofstream cout(#x ".out");
#endif

template<class T1, class T2>
istream& operator>>(istream& in, pair<T1, T2>& p) {
  return in >> p.first >> p.second;
}

template<class T1, class T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& p) {
  return out << p.first << ' ' << p.second;
}

template<size_t I = 0, typename... Ts>
typename enable_if<I == sizeof...(Ts), istream&>::type
read_tuple(istream& in, tuple<Ts...>& t) { return in; }

template<size_t I = 0, typename... Ts>
typename enable_if<I < sizeof...(Ts), istream&>::type
read_tuple(istream& in, tuple<Ts...>& t) {
  in >> get<I>(t);
  return read_tuple<I + 1>(in, t);
}

template<typename... Ts>
istream& operator>>(istream& in, tuple<Ts...>& t) {
  return read_tuple(in, t);
}

template<size_t I = 0, typename... Ts>
typename enable_if<I == sizeof...(Ts), void>::type
write_tuple(ostream& out, const tuple<Ts...>&) {}

template<size_t I = 0, typename... Ts>
typename enable_if<I < sizeof...(Ts), void>::type
write_tuple(ostream& out, const tuple<Ts...>& t) {
  if (I) out << ' ';
  out << get<I>(t);
  write_tuple<I + 1>(out, t);
}

template<typename... Ts>
ostream& operator<<(ostream& out, const tuple<Ts...>& t) {
  write_tuple(out, t);
  return out;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& v) {
  for (auto& x : v) in >> x;
  return in;
}

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& v) {
  for (size_t i = 0; i < v.size(); ++i)
    out << (i ? " " : "") << v[i];
  return out;
}

ll n, m, s, t, u, v, dist[100001], dist2[100001], dist3[100001];
bool flag[100001];
vector<pll> adj[100001];
vector<ll> from[100001], to[100001];
priority_queue<pll, vector<pll>, greater<pll>> pq;
queue<int> q;

int main() {
  bruh;
  cin >> n >> m >> s >> t >> u >> v;
  while (m--) {
    static int u, v, w; cin >> u >> v >> w;
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});
  }
  memset(dist, 0x3f, sizeof dist);
  pq.push({dist[s] = 0, s});
  while (!pq.empty()) {
    auto [d, u] = pq.top(); pq.pop();
    if (d > dist[u]) continue;
    for (auto [v, w]: adj[u]) {
      if (dist[v] > dist[u] + w) {
        pq.push({dist[v] = dist[u] + w, v});
        from[v].clear();
      }
      if (dist[v] >= dist[u] + w) {
        from[v].push_back(u);
      }
    }
  }
  memset(dist, 0x3f, sizeof dist);
  pq.push({dist[u] = 0, u});
  while (!pq.empty()) {
    auto [d, u] = pq.top(); pq.pop();
    if (d > dist[u]) continue;
    for (auto [v, w]: adj[u]) if (dist[v] > dist[u] + w) pq.push({dist[v] = dist[u] + w, v});
  }
  flag[t] = 1; q.push(t);
  while (!q.empty()) {
    auto u = q.front(); q.pop();
    for (auto v: from[u]) to[v].push_back(u);
    for (auto v: from[u]) if (!flag[v]) flag[v] = 1, q.push(v);
  }
  memset(dist2, 0x3f, sizeof dist2);
  pq.push({dist2[t] = dist[t], t});
  while (!pq.empty()) {
    auto [d, u] = pq.top(); pq.pop();
    if (d > dist2[u]) continue;
    for (auto v: from[u]) {
      int dd = min(dist[v], dist2[u]);
      if (dist2[v] > dd) pq.push({dist2[v] = dd, v});
    }
  }
  memset(dist3, 0x3f, sizeof dist3);
  pq.push({dist3[s] = dist[s], s});
  while (!pq.empty()) {
    auto [d, u] = pq.top(); pq.pop();
    if (d > dist3[u]) continue;
    for (auto v: to[u]) {
      int dd = min(dist[v], dist3[u]);
      if (dist3[v] > dd) pq.push({dist3[v] = dd, v});
    }
  }
  for (int i = 1; i <= n; i++) {
    if (dist[i] > min(dist2[i], dist3[i])) pq.push({dist[i] = min(dist2[i], dist3[i]), i});
  }
  while (!pq.empty()) {
    auto [d, u] = pq.top(); pq.pop();
    if (d > dist[u]) continue;
    for (auto [v, w]: adj[u]) if (dist[v] > dist[u] + w) pq.push({dist[v] = dist[u] + w, v});
  }
  cout << dist[v];
}

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