Submission #756879

#	Time	Username	Problem	Language	Result	Execution time	Memory
756879		NeroZein	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	498 ms	23980 KiB

commuter_pass

#include "bits/stdc++.h"
#define int long long
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

using T = pair<int, int>;

const int N = 100005;

int n, m;
vector<pair<int, int>> g[N]; 

vector<long long> dijk (int src) {
  priority_queue<T, vector<T>, greater<T>> pq; 
  vector<long long> cost(n + 1, 1e17); 
  pq.emplace(0, src);
  cost[src] = 0; 
  while (!pq.empty()) {
    auto [c, v] = pq.top();
    pq.pop();
    if (cost[v] < c) {
      continue; 
    }
    for (auto [u, w] : g[v]) {
      if (c + w < cost[u]) {
        cost[u] = c + w; 
        pq.emplace(cost[u], u); 
      }
    }
  }
  return cost; 
}

signed main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> m;
  int s, t;
  cin >> s >> t;
  int uu, vv;
  cin >> uu >> vv; 
  for(int i = 0; i < m; ++i) {
    int x, y, w;
    cin >> x >> y >> w;
    g[x].emplace_back(y, w);
    g[y].emplace_back(x, w);
  }
  auto cu = dijk(uu);
  auto cv = dijk(vv);
  long long ans = cu[vv]; 
  for (int it = 0; it < 2; ++it) {
    priority_queue<T, vector<T>, greater<T>> pq; 
    auto ct = dijk(t);
    vector<long long> cs(n + 1, 1e17); 
    vector<long long> dp(n + 1, 1e17); 
    dp[s] = cu[s];
    pq.emplace(0, s);
    cs[s] = 0; 
    while (!pq.empty()) {
      auto [c, v] = pq.top();
      pq.pop();
      if (cs[v] < c) {
        continue; 
      }
      for (auto [u, w] : g[v]) {
        if (c + w < cs[u]) {
          cs[u] = c + w;
          pq.emplace(cs[u], u); 
          dp[u] = min(dp[v], cu[u]);
        }
        if (c + w == cs[u]) {
          dp[u] = min({dp[u], dp[v], cu[u]});
        }
      }
    }
    for (int i = 1; i <= n; ++i) {
      if (ct[i] + cs[i] == ct[s]) {
        ans = min(ans, cv[i] + dp[i]); //u -> x -> i -> v
      }
    }
    swap(s, t); 
  }
  cout << ans << '\n';
  return 0;
}

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