Submission #990984

#	Time	Username	Problem	Language	Result	Execution time	Memory
990984		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	682 ms	262144 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

// #pragma GCC optimize ("O3")
// #pragma GCC optimize ("unroll-loops")

#ifdef LOCAL
  #include "algo/debug.h"
#else
  #define debug(...) 42
#endif

using ll = long long;
using db = long double; // or double, if TL is tight
#define int ll

// pairs
#define mp make_pair
#define f first
#define s second

// vectors
#define sz(v) (int)((v).size())
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

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

  int n, m; cin >> n >> m;

  vector<int> meet(4);
  for (auto &v: meet)
    cin >> v;

  vector<tuple<int, int, int>> ed;
  vector<vector<pair<int, int>>> adj(n + 1);
  for (int i = 0; i < m; i++) {
    int u, v, w; cin >> u >> v >> w;
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});
    ed.emplace_back(u, v, w);
  }
  
  const int INF = 1e18;
  
  vector dis(4, vector<int>(n + 1, INF));
  auto dijkstra = [&](int id) {
    using T = pair<int, int>;
    priority_queue<T, vector<T>, greater<T>> pq;
    auto add = [&](int d, int x) {
      if (dis[id][x] < d) return;
      pq.push({dis[id][x] = d, x});
    };
    add(0, meet[id]);
    while (!pq.empty()) {
      auto [d, u] = pq.top(); pq.pop();
      if (dis[id][u] < d) continue;
      for (auto &[v, w]: adj[u])
        add(d + w, v);
    }
  };

  for (int i = 0; i < 4; i++)
    dijkstra(i);

  vector<vector<int>> adjDAG(n + 1);
  for (auto &[u, v, w]: ed) {
    if (dis[0][u] + dis[1][v] + w == dis[0][meet[1]])
      adjDAG[v].push_back(u);
    
    if (dis[0][v] + dis[1][u] + w == dis[0][meet[1]])
      adjDAG[u].push_back(v);
  }

  vector<int> order;
  vector<bool> vis(n + 1);
  auto dfs = [&](auto self, int u) -> void {
    vis[u] = true;
    for (auto &v: adjDAG[u]) if (!vis[v])
      self(self, v);
    order.push_back(u);
  };

  for (int i = 1; i <= n; i++)
    if (!vis[i] && sz(adjDAG[i]) > 0)
      dfs(dfs, i);
  
  int res = dis[2][meet[3]];

  vector dp(2, vector<int>(n + 1));
  for (auto &u: order) {
    dp[0][u] = dis[2][u], dp[1][u] = dis[3][u];
    for (auto &v: adjDAG[u]) {
      dp[0][u] = min(dp[0][u], dp[0][v]);
      dp[1][u] = min(dp[1][u], dp[1][v]);
    }

    res = min(res, dp[0][u] + dis[3][u]);
    res = min(res, dp[1][u] + dis[2][u]);
  }

  cout << res << "\n";
}

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