Submission #1009004

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009004		devariaota	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	2032 ms	18372 KiB

commuter_pass

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;

const int inf = 1e18;

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m, a, b, c, d;
  cin >> n >> m >> a >> b >> c >> d;
  vector<vector<pair<int, int>>> adj(n + 5);
  while (m--) {
    int u, v, w;
    cin >> u >> v >> w;
    adj[u].emplace_back(w, v);
    adj[v].emplace_back(w, u);
  }

  /*
  
  dijkstra dari a ke b
  track back jalurnya
  array boolean jalur optimal
  dist[optimal] = min. dari c ke semua optimal
  dijkstra multisource yaitu b dan semua nodes jalur optimal

  problem: kalau jalur optimal lebih dari satu, mau pake yg mana
  sol:
  - dijkstra from d
  - dilihat dist from c + dist from d paling minimal

  */

  vector<int> dist(n + 5, inf);
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

  dist[a] = 0;
  pq.emplace(dist[a], a);

  while (!pq.empty()) {
    int cur = pq.top().se, wei = pq.top().fi;
    pq.pop();

    if (wei > dist[cur]) {
      continue;
    }

    for (auto &i : adj[cur]) {
      if (dist[i.se] > dist[cur] + i.fi) {
        dist[i.se] = dist[cur] + i.fi;
        pq.emplace(dist[i.se], i.se);
      }
    }
  }

  vector<bool> opt(n + 5);
  queue<int> q;
  q.push(b);
  while (!q.empty()) {
    int bre = q.size();
    set<int> st;
    while (bre--) {
      int cur = q.front();
      q.pop();

      opt[cur] = true;

      for (auto &i : adj[cur]) {
        if (dist[cur] == dist[i.se] + i.fi) {
          st.insert(i.se);
        }
      }
      
    }
    for (auto &i : st) {
      q.push(i);
    }
  }

  // subsoal 1
  if (a == c) {
    for (int i = 1; i <= n; ++i) {
      dist[i] = inf;
    }

    dist[d] = 0;
    pq.emplace(dist[d], d);

    while (!pq.empty()) {
      int cur = pq.top().se, wei = pq.top().fi;
      pq.pop();
    
      if (wei > dist[cur]) {
        continue;
      }

      for (auto &i : adj[cur]) {
        if (dist[i.se] > dist[cur] + i.fi) {
          dist[i.se] = dist[cur] + i.fi;
          pq.emplace(dist[i.se], i.se);
        }
      }
    }

    int ans = inf;
    for (int i = 1; i <= n; ++i) {
      if (opt[i]) {
        ans = min(ans, dist[i]);
      }
    }
    cout << ans << '\n';

    return 0;
  }

  for (int i = 1; i <= n; ++i) {
    dist[i] = inf;
  }
  dist[c] = 0;
  pq.emplace(dist[c], c);

  while (!pq.empty()) {
    int cur = pq.top().se, wei = pq.top().fi;
    pq.pop();
    
    if (wei > dist[cur]) {
      continue;
    }

    for (auto &i : adj[cur]) {
      if (dist[i.se] > dist[cur] + i.fi) {
        dist[i.se] = dist[cur] + i.fi;
        pq.emplace(dist[i.se], i.se);
      }
    }
  }

  int mn = inf;
  for (int i = 1; i <= n; ++i) {
    if (opt[i]) {
      mn = min(mn, dist[i]);
    }
  }

  for (int i = 1; i <= n; ++i) {
    dist[i] = inf;
  }
  dist[c] = 0;
  pq.emplace(dist[c], c);

  // ===== INI SALAH cuz blm tentu dari node optimal ke node optimal lain bisa segitu =====
  for (int i = 1; i <= n; ++i) {
    if (opt[i]) {
      dist[i] = mn;
      pq.emplace(dist[i], i);
    }
  }

  while (!pq.empty()) {
    int cur = pq.top().se, wei = pq.top().fi;
    pq.pop();

    if (wei > dist[cur]) {
      continue;
    }

    for (auto &i : adj[cur]) {
      if (dist[i.se] > dist[cur] + i.fi) {
        dist[i.se] = dist[cur] + i.fi;
        pq.emplace(dist[i.se], i.se);
      }
    }
  }

  cout << dist[d] << '\n';

  return 0;
}

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