Submission #1000228

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000228		ALTAKEXE	Train (APIO24_train)	C++17	5 / 100	57 ms	15932 KiB

train

#include <bits/stdc++.h>
#define ll long long
using namespace std;
vector<array<int, 4>> adj[200005];
ll dist[200005];
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)
{
  for (int i = 0; i < n; i++)
    adj[i].clear();
  for (int i = 0; i < m; i++)
    adj[X[i]].push_back({A[i], B[i], Y[i], C[i]});
  for (int i = 0; i < n; i++)
    sort(adj[i].begin(), adj[i].end());
  dist[0] = 0;
  for (int i = 1; i < n; i++)
    dist[i] = LLONG_MAX;
  priority_queue<array<ll, 3>, vector<array<ll, 3>>, greater<array<ll, 3>>> pq;
  pq.push({0, 0, 0});
  while (pq.size())
  {
    auto [cost, tim, node] = pq.top();
    pq.pop();
    if (cost > dist[node])
      continue;
    dist[node] = cost;
    for (auto [l, r, y, c] : adj[node])
      if (l >= tim && cost + c < dist[y])
        pq.push({cost + c, r, y});
  }
  return (dist[n - 1] == LLONG_MAX ? -1 : dist[n - 1]);
}

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