Submission #1130097

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130097		shaggy456	Commuter Pass (JOI18_commuter_pass)	C++20	55 / 100	373 ms	50800 KiB

commuter_pass

#include <bits/stdc++.h>
#include <climits>
#include <cmath>
#include <cstdarg>

using namespace std;

using ll = long long;
using vl = vector<ll>;
using pll = pair<ll, ll>;

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

void setIO(const string &filename = "") {
  ios::sync_with_stdio(false);
  cin.tie(0);

  if (!filename.empty()) {
    freopen((filename + ".in").c_str(), "r", stdin);
    freopen((filename + ".out").c_str(), "w", stdout);
  }
}

using ll = long long;
using pll = pair<ll, ll>;

class dsu {
public:
  vector<int> parent;
  dsu(int n) {
    parent.resize(n);
    fill(parent.begin(), parent.end(), -1);
  }
  int find(int x) {
    if (parent[x] < 0)
      return x;
    parent[x] = find(parent[x]);
    return parent[x];
  }
  bool unite(int x, int y) {
    int a = find(x);
    int b = find(y);
    if (a == b)
      return false;
    if (parent[a] > parent[b]) {
      swap(a, b);
    }
    parent[a] += parent[b];
    parent[b] = a;
    return true;
  }
};
void dfs(int curr, vector<vector<int>> const &graph, vector<bool> &seen,
         vector<int> &res) {
  seen[curr] = true;
  for (auto n : graph[curr]) {
    if (seen[n])
      continue;
    dfs(n, graph, seen, res);
  }
  res.push_back(curr);
}
unordered_set<int> solve(int n, int m) {
  vector<vector<int>> out(n + 1);
  vector<vector<int>> inc(n + 1);
  for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    out[x].push_back(y);
    inc[y].push_back(x);
  }
  vector<int> res;
  vector<bool> seen(n + 1);
  for (int i = 1; i <= n; i++) {
    if (seen[i])
      continue;
    dfs(i, out, seen, res);
  }
  reverse(res.begin(), res.end());

  vector<unordered_set<int>> dp(n + 1);
  dp[1].insert(0);
  for (auto node : res) {
    for (auto n : inc[node]) {
      for (auto val : dp[n]) {
        dp[node].insert(val + 1);
      }
    }
  }
  return dp[n];
}

const ll INF = LLONG_MAX / 2;

int main() {
  setIO();
  int n, m;
  cin >> n >> m;
  int s, t;
  cin >> s >> t;
  int u, v;
  cin >> u >> v;

  vector<vector<pll>> graph(n + 1);

  for (int i = 0; i < m; i++) {
    ll a, b, c;
    cin >> a >> b >> c;
    graph[a].push_back({b, c});
    graph[b].push_back({a, c});
  }

  vector<ll> dist(n + 1, INF);
  vector<vector<ll>> parents(n + 1);

  dist[s] = 0;

  priority_queue<pll, vector<pll>, greater<pll>> pq;
  pq.push({0, s});
  vector<bool> visited(n + 1);
  while (!pq.empty()) {
    auto curr = pq.top().second;
    pq.pop();
    if (visited[curr])
      continue;
    visited[curr] = true;
    for (auto [next, w] : graph[curr]) {
      if (dist[curr] + w < dist[next]) {
        dist[next] = dist[curr] + w;
        parents[next].clear();
        parents[next].push_back(curr);
        pq.push({dist[next], next});
      } else if (dist[curr] + w == dist[next]) {
        parents[next].push_back(curr);
      }
    }
  }
  vector<vector<ll>> out(n + 1);
  vector<vector<ll>> inc(n + 1);

  queue<int> q;
  vector<bool> seen(n + 1);
  q.push(t);
  while (!q.empty()) {
    auto curr = q.front();
    q.pop();
    if (seen[curr])
      continue;
    seen[curr] = true;
    for (auto parent : parents[curr]) {
      inc[parent].push_back(curr);
      out[curr].push_back(parent);
      q.push(parent);
    }
  }

  array<ll, 4> d = {INF, INF, INF, INF};
  vector<array<ll, 4>> dist2(n + 1, d);
  dist2[u][0] = 0;
  pq.push({0, u});
  fill(visited.begin(), visited.end(), false);
  while (!pq.empty()) {
    auto curr = pq.top().second;
    pq.pop();
    if (visited[curr])
      continue;
    visited[curr] = true;
    for (auto [next, w] : graph[curr]) {
      ll x = w + dist2[curr][0];
      ll y = w + min(dist2[curr][1], dist2[curr][2]);
      ll z = w + dist2[curr][3];
      if (x < dist2[next][0]) {
        dist2[next][0] = x;
        pq.push({dist2[next][0], next});
      }
      if (y < dist2[next][3]) {
        dist2[next][3] = y;
        pq.push({dist2[next][3], next});
      }
      if (z < dist2[next][3]) {
        dist2[next][3] = z;
        pq.push({dist2[next][3], next});
      }
    }
    for (auto next : out[curr]) {
      if (dist2[curr][0] < dist2[next][1]) {
        dist2[next][1] = dist2[curr][0];
        pq.push({dist2[next][1], next});
      }
      if (dist2[curr][1] < dist2[next][1]) {
        dist2[next][1] = dist2[curr][1];
        pq.push({dist2[next][1], next});
      }
    }
    for (auto next : inc[curr]) {
      if (dist2[curr][0] < dist2[next][2]) {
        dist2[next][2] = dist2[curr][0];
        pq.push({dist2[next][2], next});
      }
      if (dist2[curr][2] < dist2[next][2]) {
        dist2[next][2] = dist2[curr][2];
        pq.push({dist2[next][2], next});
      }
    }
  }
  ll val = *min_element(dist2[v].begin(), dist2[v].end());
  cout << val << '\n';

  return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void setIO(const string&)':
commuter_pass.cpp:20:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     freopen((filename + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:21:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |     freopen((filename + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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