Submission #1099322

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099322		akamizane	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	308 ms	36308 KiB

commuter_pass

#include<bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
using pii = pair<int,long long>;
 
#define el cout << '\n'
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, n) for (int i = 0; i < (n); i++)
template <class T1, class T2>bool chmax(T1 &a, T2 b){return a < b ? a = b, 1 : 0;}
template <class T1, class T2>bool chmin(T1 &a, T2 b){return a > b ? a = b, 1 : 0;}
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const ll mod = 1e9 + 7;

const int maxn = 1e5 + 5;

void solve(){
  int n, m, s1, e1, s2, e2;
  cin >> n >> m >> s1 >> e1 >> s2 >> e2;
  vector<vector<pii>> ad(n + 1);
  REP(i, m){
    int u, v;
    ll w;
    cin >> u >> v >> w;
    ad[u].pb({v, w});
    ad[v].pb({u, w});
  }
  using T = pair<long long, int>;
  vector<vector<int>> dag(n + 1);
  vector<ll> d(n + 1, 1e18);
  priority_queue<T, vector<T>, greater<T>> pq;
  pq.push({0, s1});
  d[s1] = 0;
  while(pq.size()){
    auto [val, u] = pq.top();
    pq.pop();
    if (val != d[u]) continue;
    for (auto [v, w] : ad[u]){
      if (val + w < d[v]){
        d[v] = val + w;
        dag[v] = {u};
        pq.push({d[v], v});
      }
      else if (val + w == d[v]){
        dag[v].pb(u);
      }
    }
  }
  vector<vector<ll>> dis(n + 1, vector<ll> (2, 1e18));
  for (int cnt = 0; cnt < 2; cnt++){
    int cur = (cnt == 0 ? s2 : e2);
    dis[cur][cnt] = 0;
    pq.push({0, cur});
    while(pq.size()){
      auto [val, u] = pq.top();
      pq.pop();
      if (val != dis[u][cnt]) continue;
      for (auto [v, w] : ad[u]){
        if (val + w < dis[v][cnt]){
          dis[v][cnt] = val + w;
          pq.push({dis[v][cnt], v});
        }
      }
    }
  }
  const ll INF = 1e18;
  ll res = dis[e2][0];
  using pll = array<long long, 2>;
  vector<pll> dp(n + 1, {INF, INF});
  vector<bool> vis(n + 1);
  function<void(int)> dfs = [&](int u) {
    if (vis[u]) return;
    vis[u] = true;
    dp[u] = {dis[u][0], dis[u][1]};
    for (int v : dag[u]) {
        dfs(v);
        for (int id = 0; id < 2; id++) {
        chmin(dp[u][id], dp[v][id]);
      }
    }
    for (int id = 0; id < 2; id++) {
        chmin(res, dis[u][id] + dp[u][!id]);
    }
  };
  dfs(e1);
  cout << res;
}
 
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int tests = 1;
  // cin >> tests;
  for (int _ = 1; _ <= tests; _++){
    cerr << "- Case #" << _ << ": \n";
    solve();
    el;
  }
  return 0;
}

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