| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1362750 | opeleklanos | Train (APIO24_train) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#include "train.h"
#define ll long long
#define INF (ll)100000000000000000000
struct route{
ll t1;
ll t0;
ll from;
ll dest;
ll cost;
ll totalCost;
};
vector<vector<ll>> adj;
vector<pair<ll, ll>> meals;
vector<vector<ll>> dp;
long long solve(ll N, ll M, ll W, vector<ll> T, vector<ll> X, vector<ll> Y,
vector<ll> A, vector<ll> B, vector<ll> C, vector<ll> L, vector<ll> R){
adj.assign(N, {});
vector<route> paths;
for(ll i = 0; i<M; i++){
adj[X[i]].push_back(i);
adj[Y[i]].push_back(i);
paths.push_back({B[i], A[i], X[i], Y[i], C[i], 1000000000});
}
for(ll i = 0; i<W; i++) meals.push_back({L[i], R[i]});
sort(meals.begin(), meals.end());
for(ll i = 0; i<M; i++){
for(auto j : adj[paths[i].from]){
if(paths[j].dest == paths[i].from && paths[j].t1 <= paths[i].t0){
paths[i].totalCost = min(paths[i].totalCost, paths[j].totalCost + paths[j].cost);
}
}
}
ll ans = 1000000000;
for(ll i = 0; i<M; i++){
if(paths[i].dest == N-1) ans = min(ans, paths[i].totalCost);
}
return ans;
}