#include <vector>
#include <queue>
#include <algorithm>
#include <limits>
#include <iostream>
#include <set>
using namespace std;
const long long INF = 1e18;
struct Train {
int x, y;
long long a, b, c;
int id;
};
struct Event {
long long time;
int type; // 0: departure, 1: arrival
int train_id;
bool operator<(const Event& other) const {
if (time != other.time) return time < other.time;
return type < other.type;
}
};
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) {
// Preprocess trains
vector<Train> trains(M);
for (int i = 0; i < M; i++) {
trains[i] = {X[i], Y[i], A[i], B[i], C[i], i};
}
// Sort trains by departure time
sort(trains.begin(), trains.end(), [](const Train& t1, const Train& t2) {
return t1.a < t2.a;
});
// For each planet, store available arrival times and costs
vector<vector<pair<long long, long long>>> planet_arrivals(N);
vector<long long> dist(N, INF);
dist[0] = 0;
// Priority queue for Dijkstra: (cost, planet, time)
using State = tuple<long long, int, long long>;
priority_queue<State, vector<State>, greater<State>> pq;
pq.push({0, 0, 0});
// Process trains in chronological order
vector<long long> best_cost_to_planet(N, INF);
best_cost_to_planet[0] = 0;
// Group trains by departure planet
vector<vector<Train>> departures(N);
for (const auto& train : trains) {
departures[train.x].push_back(train);
}
// For each planet, maintain the best cost to reach it at any time
vector<long long> min_cost(N, INF);
min_cost[0] = 0;
// Process in chronological order of events
vector<Event> events;
for (int i = 0; i < M; i++) {
events.push_back({trains[i].a, 0, i}); // departure
events.push_back({trains[i].b, 1, i}); // arrival
}
sort(events.begin(), events.end());
// Track best cost to reach each planet at any time
vector<long long> planet_min_cost(N, INF);
planet_min_cost[0] = 0;
// Process events in chronological order
for (const auto& event : events) {
const Train& train = trains[event.train_id];
if (event.type == 0) { // departure
// Can we take this train?
if (planet_min_cost[train.x] != INF) {
// We can board this train from planet x
long long new_cost = planet_min_cost[train.x] + train.c;
// Update arrival planet if this gives better cost
if (new_cost < planet_min_cost[train.y]) {
planet_min_cost[train.y] = new_cost;
}
}
} else { // arrival
// When train arrives, we update the min cost for the arrival planet
// The cost to reach planet y is min of current cost and cost via this train
// But we need to consider if we had a valid path to departure planet
// This is already handled by the departure event processing
}
}
// If we cannot reach destination
if (planet_min_cost[N-1] == INF) {
return -1;
}
// Now handle meals
// For each meal, check if it can be taken on any train for free
vector<bool> meal_covered(W, false);
// Create time intervals for all trains
vector<pair<long long, long long>> train_intervals;
for (const auto& train : trains) {
train_intervals.push_back({train.a, train.b});
}
// Sort train intervals and merge overlapping intervals
sort(train_intervals.begin(), train_intervals.end());
vector<pair<long long, long long>> merged;
for (const auto& interval : train_intervals) {
if (merged.empty() || merged.back().second < interval.first) {
merged.push_back(interval);
} else {
merged.back().second = max(merged.back().second, interval.second);
}
}
// For each meal, check if it fits in any train interval
for (int i = 0; i < W; i++) {
long long l = L[i], r = R[i];
// Binary search to find if any train interval covers [l, r]
int left = 0, right = merged.size() - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (merged[mid].second < l) {
left = mid + 1;
} else if (merged[mid].first > r) {
right = mid - 1;
} else {
// Overlap exists, check if full coverage
if (merged[mid].first <= l && merged[mid].second >= r) {
meal_covered[i] = true;
break;
}
// Check neighboring intervals too
if (mid > 0 && merged[mid-1].first <= l && merged[mid-1].second >= r) {
meal_covered[i] = true;
break;
}
if (mid < merged.size()-1 && merged[mid+1].first <= l && merged[mid+1].second >= r) {
meal_covered[i] = true;
break;
}
break;
}
}
}
// Calculate additional meal cost
long long additional_meal_cost = 0;
// For meals not covered by trains, we need to take them on planets
// We need to find the cheapest planet where we spend enough time to take the meal
// This is complex - for simplicity, let's use the minimum planet cost among visited planets
// Find all planets reachable in the optimal path
// For simplicity in this implementation, use the minimum T among all planets
// that appear in any train route from the optimal path
// Simplified approach: use global min T
int min_T = *min_element(T.begin(), T.end());
for (int i = 0; i < W; i++) {
if (!meal_covered[i]) {
additional_meal_cost += min_T;
}
}
return planet_min_cost[N-1] + additional_meal_cost;
}
