Submission #518425

#	Time	Username	Problem	Language	Result	Execution time	Memory
518425		Alex_tz307	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	253 ms	19460 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

const int kN = 1e5;
const int64_t INF = 2e18L;
int n;
vector<pair<int, int>> g[1 + kN];
int64_t ans, du[1 + kN], dv[1 + kN];

void minSelf(int64_t &x, int64_t y) {
  if (y < x) {
    x = y;
  }
}

void Dijkstra(int s, int64_t d[]) {
  for (int v = 1; v <= n; ++v) {
    d[v] = INF;
  }
  priority_queue<pair<int64_t, int>, vector<pair<int64_t, int>>, greater<pair<int64_t, int>>> pq;
  d[s] = 0;
  pq.emplace(0, s);
  while (!pq.empty()) {
    int64_t cost;
    int u;
    tie(cost, u) = pq.top();
    pq.pop();
    if (cost != d[u]) {
      continue;
    }
    for (auto it : g[u]) {
      int v, w;
      tie(v, w) = it;
      if (d[v] > d[u] + w) {
        d[v] = d[u] + w;
        pq.emplace(d[v], v);
      }
    }
  }
}

void solve(int s, int t) {
  /// drumul optim de la u la v poate sa intersecteze un drum continut intr-un drum de cost minim de la s la t
  /// dp[node][0 / 1] =def= u si v se deplaseaza pana la cate un nod de pe un ACELASI drum de cost
  /// minim de la s la node astfel incat dp[node][0] + dp[node][1] este minim(ma intereseaza doar cat
  /// au de facut pana la nodurile respective pentru ca intre ele folosesc commuter-ul si va fi gratis)
  /// in timp ce fac drumul minim de la s la t actualizez dinamica
  vector<int64_t> d(n + 1, INF);
  vector<vector<int64_t>> dp(n + 1, vector<int64_t>(2, INF));
  dp[s][0] = du[s];
  dp[s][1] = dv[s];
  priority_queue<pair<int64_t, int>, vector<pair<int64_t, int>>, greater<pair<int64_t, int>>> pq;
  d[s] = 0;
  pq.emplace(0, s);
  while (!pq.empty()) {
    int64_t cost;
    int from;
    tie(cost, from) = pq.top();
    pq.pop();
    if (cost != d[from]) {
      continue;
    }
    for (auto it : g[from]) {
      int to, w;
      tie(to, w) = it;
      if (d[to] > d[from] + w) {
        dp[to][0] = min(dp[from][0], du[to]);
        dp[to][1] = min(dp[from][1], dv[to]);
        d[to] = d[from] + w;
        pq.emplace(d[to], to);
      } else if (d[to] == d[from] + w) {
        if (dp[to][0] + dp[to][1] > min(dp[from][0], du[to]) + min(dp[from][1], dv[to])) {
          dp[to][0] = min(dp[from][0], du[to]);
          dp[to][1] = min(dp[from][1], dv[to]);
        }
      }
    }
  }
  minSelf(ans, dp[t][0] + dp[t][1]);
}

void testCase() {
  int m, s, t, u, v;
  cin >> n >> m >> s >> t >> u >> v;
  for (int i = 0; i < m; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    g[u].emplace_back(v, w);
    g[v].emplace_back(u, w);
  }
  Dijkstra(u, du);
  Dijkstra(v, dv);
  ans = du[v]; /// poate drumul optim de la u la v este cel direct dintre ele fara commuter pass
  solve(s, t); /// u - x - y - v
  cout << ans << '\n';
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int tests = 1;
  for (int tc = 0; tc < tests; ++tc) {
    testCase();
  }
  return 0;
}

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