Submission #1179969

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179969		avighna	Train (APIO24_train)	C++20	5 / 100	649 ms	53516 KiB

train

#include "train.h"

#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <vector>

const long long inf = 1e15;

long long solve(int N, int M, int W, std::vector<int> T, std::vector<int> X,
                std::vector<int> Y, std::vector<int> A, std::vector<int> B,
                std::vector<int> C, std::vector<int> L, std::vector<int> R) {
  std::vector<std::vector<int>> node_times(N);
  std::map<std::pair<int, int>,
           std::vector<std::pair<std::pair<int, int>, int>>>
      adj;
  for (int i = 0; i < M; ++i) {
    node_times[X[i]].push_back(A[i]);
    node_times[Y[i]].push_back(B[i]);
    adj[{X[i], A[i]}].push_back({{Y[i], B[i]}, C[i]});
  }
  node_times[0].push_back(0);
  for (int i = 0; i < N; ++i) {
    std::sort(node_times[i].begin(), node_times[i].end());
    for (int j = 1; j < node_times[i].size(); ++j) {
      adj[{i, node_times[i][j - 1]}].push_back({{i, node_times[i][j]}, 0});
    }
  }

  std::set<std::pair<int, int>> vis;
  std::map<std::pair<int, int>, long long> ans;
  ans[{0, 0}] = 0;
  std::priority_queue<std::pair<long long, std::pair<int, int>>> pq;
  pq.push({0, {0, 0}});
  while (!pq.empty()) {
    auto [dist, u] = pq.top();
    pq.pop();
    if (vis.count(u)) {
      continue;
    }
    vis.insert(u);
    dist = -dist;
    for (auto &i : adj[u]) {
      if (!ans.count(i.first)) {
        ans[i.first] = inf;
      }
      if (dist + i.second < ans[i.first]) {
        ans[i.first] = dist + i.second;
        pq.push({-ans[i.first], i.first});
      }
    }
  }
  if (node_times[N - 1].empty()) {
    return -1;
  }
  long long ret = ans[{N - 1, node_times[N - 1].back()}];
  if (ret == inf) {
    ret = -1;
  }
  return ret;
}

• Subtask 1: 0 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 30
• Subtask 4: 0 / 60