Submission #1009281

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009281		christinelynn	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	2039 ms	39340 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;

struct DSU {
  vector<int> p, sz; 
  vector<set<int>> children;
  DSU(int n) {
    p = vector<int>(n);
    children = vector<set<int>>(n, set<int>());
    // mn = vector<int>(n);
    for(int i = 0; i < n; i++) {
      p[i] = i;
      children[i].insert(i);
    }
  }

  int find(int a) {
    if (a == p[a]) return p[a];
    return p[a] = find(p[a]);
  }

  void join(int a, int b) {
    int r1 = find(a);
    int r2 = find(b);
    if (r1 == r2) return;
    p[r1] = r2;
    
    if (children[r1].size() > children[r2].size()) swap(children[r1], children[r2]);
    for (auto x : children[r1]) children[r2].insert(x);
  }
};

void solve() {
  int n,m;cin>>n>>m;
  int s,t,u,v;cin>>s>>t>>u>>v;s--;t--;u--;v--;
  DSU dsu(n);

  vector<vector<pair<int, int>>> adj(n, vector<pair<int, int>>());
  for (int i = 0; i < m; i++) {
    int u,v,w;cin>>u>>v>>w;u--;v--;
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});
  }

  // djikstra from s
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int,int>>> pq;
  pq.push({0, s});
  vector<int> dist(n, INF);
  
  while (!pq.empty()) {
    auto [cost, node] = pq.top();pq.pop();
    if (cost > dist[node]) continue;
    dist[node] = cost;
    for (auto [children, w] : adj[node]) {
      if (cost+w < dist[children]) {
        dist[children] = cost+w;
        pq.push({cost+w, children});
      }
    }
  }

  
  // mundur dari T, dan join
  vector<int> vis(n);
  function<void(int)> dfs = [&](int node) {
    vis[node] = 1;
    for (auto [children, w] : adj[node]) {
      if (dist[node] - w == dist[children]) {
        dfs(children);
        dsu.join(children, t);
      } 
    }
  };

  // for (auto el : dist) cout << el << " ";
  // cout << endl;
  dfs(t);

  // habis itu djikstra dari U -> V lagi

  vector<int> dp(n, INF);
  // pq.clear();
  pq.push({0, u});
  while (!pq.empty()) {
    auto [cost, node] = pq.top();pq.pop();
    int r = dsu.find(node);
    if (cost > dp[r]) continue;
    dp[r] = cost;

    if (dsu.children[r].count(v)) {
      cout << cost << endl;
      return;
    }

    for (auto x : dsu.children[r]) {
      for (auto [children, w] : adj[x]) {
        if (cost+w < dp[dsu.find(children)]) {
          dp[children] = cost+w; 
          pq.push({cost+w, dsu.find(children)});
        }
      }
    }
  }
  // for (auto el : dp) cout << el << " ";
}

int32_t main() {
  ios_base::sync_with_stdio(0);cin.tie(0);
  int t=1;
  while(t--) solve();

  return 0;
}

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