結果
| 問題 |
No.2366 登校
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 12:58:30 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 516 ms / 4,000 ms |
| コード長 | 12,837 bytes |
| コンパイル時間 | 1,490 ms |
| コンパイル使用メモリ | 132,360 KB |
| 実行使用メモリ | 324,864 KB |
| 最終ジャッジ日時 | 2025-06-20 11:31:59 |
| 合計ジャッジ時間 | 3,437 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 26 |
ソースコード
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <cmath>
#include <vector>
#include <utility> // For std::pair
#include <algorithm> // for std::prev
using namespace std;
// Use long long for time and fatigue values which can be large
typedef long long ll;
// Define a large constant to represent infinity.
// This needs to be large enough to not interfere with actual path costs/times.
// Given the constraints (T, C_i, D_i up to 10^9, grid size up to 80x80),
// path times and fatigues can reach values around 10^12 or higher.
// 4e18 is a safe upper bound (larger than max possible ll value / 2).
const ll INF = 4e18;
// State structure for the priority queue in Dijkstra's algorithm
struct State {
ll fatigue; // Current accumulated fatigue
ll time; // Current time elapsed (can be negative due to time rewind)
int node_idx; // Index of the current key location (in key_locations vector)
// Custom comparison operator for the priority queue (min-heap).
// Prioritizes states with lower fatigue. If fatigue is equal, prioritizes lower time.
bool operator>(const State& other) const {
if (fatigue != other.fatigue) {
return fatigue > other.fatigue; // Minimum fatigue first
}
return time > other.time; // Then minimum time
}
};
int N, M, K; // Grid dimensions, number of mysterious cells
ll T; // Time limit
// Map from the index of a key location (if it's a mysterious cell) to its parameters {C, D}
// Indices 1 to K correspond to the mysterious cells.
map<int, pair<ll, ll>> mysterious_cell_params;
vector<pair<int, int>> key_locations; // Stores coordinates {row, col} of key locations: P0 (start), P1..PK (mysterious), P(K+1) (end)
vector<vector<ll>> adj_dist; // Adjacency matrix storing shortest path distances (time cost) between key locations using only Action 1 (movement).
// Helper function to compute Manhattan distance between two grid cells
// This represents the minimum time to travel between them using only Action 1.
ll grid_dist(pair<int, int> start, pair<int, int> end) {
// Calculate Manhattan distance: |row1 - row2| + |col1 - col2|
// Cast differences to ll before adding to avoid potential intermediate overflow if N, M were very large, though not needed for N,M <= 80.
return (ll)abs(start.first - end.first) + (ll)abs(start.second - end.second);
}
int main() {
// Optimize C++ standard streams for faster input/output
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// Read input values
cin >> N >> M >> K >> T;
// Initialize key locations vector
key_locations.push_back({1, 1}); // Add start location P0 at index 0
// Read K mysterious cells and store their info
for (int i = 0; i < K; ++i) {
int r, c;
ll C_val, D_val;
cin >> r >> c >> C_val >> D_val;
key_locations.push_back({r, c}); // Add mysterious cell Pi at index i+1
// Map the node index (i+1) to its parameters C and D
mysterious_cell_params[i + 1] = {C_val, D_val};
}
key_locations.push_back({N, M}); // Add end location P(K+1) at index K+1
int num_key_locations = K + 2; // Total number of key locations
adj_dist.resize(num_key_locations, vector<ll>(num_key_locations));
// Precompute shortest path distances (Manhattan distances) between all pairs of key locations
for (int i = 0; i < num_key_locations; ++i) {
for (int j = 0; j < num_key_locations; ++j) {
adj_dist[i][j] = grid_dist(key_locations[i], key_locations[j]);
}
}
// Initialize Dijkstra's algorithm
// Priority queue stores states {fatigue, time, node_idx}, ordered by min fatigue, then min time.
priority_queue<State, vector<State>, greater<State>> pq;
// 'dist[k]' stores a map for key location k: maps fatigue level -> minimum time achieved for that fatigue level.
// This stores the non-dominated (Pareto optimal) states reached at each key location.
vector<map<ll, ll>> dist(num_key_locations);
// Start state: At P0 (index 0) with 0 fatigue and 0 time.
dist[0][0] = 0;
pq.push({0, 0, 0}); // Add initial state to the priority queue
ll final_min_fatigue = -1; // Variable to store the minimum fatigue found that satisfies the time limit T. Initialize to -1 (not found).
// Main Dijkstra loop
while (!pq.empty()) {
// Get the state with the minimum fatigue (and minimum time for ties) from the priority queue
State current = pq.top();
pq.pop();
ll fatigue = current.fatigue;
ll time = current.time;
int u = current.node_idx; // Current key location index
// Optimization: If we have already found a path to this state (u, fatigue) with a better or equal time, skip processing this one.
// Check if fatigue exists in the map for node u AND the recorded time is strictly less than the current state's time.
// If dist[u][fatigue] == time, it means this is the state we added earlier, so proceed.
if (dist[u].count(fatigue) && dist[u][fatigue] < time) {
continue;
}
// Check if the destination node (P(K+1), index K+1) is reached
if (u == K + 1) {
// If the time taken is within the limit T
if (time <= T) {
// Since the priority queue processes states in increasing order of fatigue,
// this is the first time we reach the destination satisfying the time constraint.
// Therefore, this path has the minimum possible fatigue.
final_min_fatigue = fatigue;
break; // Found the optimal solution, exit the loop.
}
// If time > T, this specific path is too slow. We need to continue searching.
// Since we are at the destination, we don't need to explore neighbors from here.
continue;
}
// Pruning optimization: If we have already found *a* valid path to the destination (final_min_fatigue != -1),
// any state we extract from the queue with fatigue >= final_min_fatigue cannot lead to a better solution (lower fatigue).
// So, we can prune this path.
if (final_min_fatigue != -1 && fatigue >= final_min_fatigue) {
continue;
}
// Explore transitions from the current state (u, fatigue, time):
// 1. Transition via Action 1: Move from current key location P_u to another key location P_v.
for (int v = 0; v < num_key_locations; ++v) {
ll travel_time = adj_dist[u][v]; // Time cost for movement
ll new_time = time + travel_time; // Calculate new time
ll new_fatigue = fatigue; // Fatigue does not change with movement
// Dominance Check: Determine if the new state (v, new_fatigue, new_time) is potentially useful or if it's dominated by existing states at node v.
bool dominated = false;
// Find the first element in dist[v] with fatigue level >= new_fatigue
auto it_lower = dist[v].lower_bound(new_fatigue);
// Check if an existing state at node v has the *same* fatigue but less or equal time.
if (it_lower != dist[v].end() && it_lower->first == new_fatigue) {
if (it_lower->second <= new_time) {
dominated = true;
}
}
// Check if an existing state at node v has *strictly less* fatigue and less or equal time.
// We need to look at the element *before* it_lower.
if (!dominated && it_lower != dist[v].begin()) {
auto it_prev = prev(it_lower); // Iterator to the element with the largest fatigue < new_fatigue
if(it_prev->second <= new_time){ // If its time is also <= new_time, it dominates.
dominated = true;
}
}
// If the new state is not dominated:
if (!dominated) {
// Update the distance map: record the new minimum time for this fatigue level at node v.
dist[v][new_fatigue] = new_time;
// Add the new state to the priority queue for further exploration.
pq.push({new_fatigue, new_time, v});
// Clean up dominated states: Remove any existing states at node v that are now dominated by this new state (new_fatigue, new_time).
// A state (f', t') is dominated if f' >= new_fatigue AND t' >= new_time (and it's not the same state).
vector<ll> fatigues_to_remove; // Store keys (fatigues) to remove safely after iteration
// Find the first element with fatigue > new_fatigue
auto it_upper = dist[v].upper_bound(new_fatigue);
// Iterate through all states with fatigue > new_fatigue
for(auto it = it_upper; it != dist[v].end(); ++it) {
// If this state's time is also >= new_time, it's dominated.
if (it->second >= new_time) {
fatigues_to_remove.push_back(it->first);
}
}
// Perform the removal of dominated states.
for (ll f_remove : fatigues_to_remove) {
dist[v].erase(f_remove);
}
}
} // End of loop exploring Action 1 transitions
// 2. Transition via Action 2: Use the time-rewind ability if P_u is a mysterious cell.
// Check if the current node index 'u' corresponds to a mysterious cell (indices 1 to K).
if (mysterious_cell_params.count(u)) {
// Retrieve the C and D parameters for this mysterious cell
ll C_val = mysterious_cell_params[u].first;
ll D_val = mysterious_cell_params[u].second;
// Calculate the effect of using Action 2 once
ll time_change = 1 - C_val; // Time changes by 1 - C_i (can be negative)
ll fatigue_increase = D_val; // Fatigue increases by D_i (>= 1)
// Basic check to prevent potential overflow when adding fatigue.
// If current fatigue is already extremely large, adding more might exceed ll limits.
if (fatigue > INF - fatigue_increase) continue; // Skip if overflow might occur
ll new_fatigue = fatigue + fatigue_increase; // Calculate new fatigue
ll new_time = time + time_change; // Calculate new time
// Dominance Check for the resulting state (u, new_fatigue, new_time) at the *same* node u.
bool dominated = false;
auto it_lower = dist[u].lower_bound(new_fatigue); // Find first state with fatigue >= new_fatigue
// Check state with same fatigue
if(it_lower != dist[u].end() && it_lower->first == new_fatigue) {
if (it_lower->second <= new_time) dominated = true;
}
// Check states with strictly smaller fatigue
if(!dominated && it_lower != dist[u].begin()){
auto it_prev = prev(it_lower);
if (it_prev->second <= new_time) dominated = true;
}
// If the resulting state is not dominated:
if (!dominated) {
// Update the distance map for node u with the new state
dist[u][new_fatigue] = new_time;
// Add the new state (staying at node u, but with updated fatigue and time) back to the priority queue
pq.push({new_fatigue, new_time, u});
// Clean up: Remove states at node u that are now dominated by this new state (new_fatigue, new_time).
vector<ll> fatigues_to_remove;
auto it_upper = dist[u].upper_bound(new_fatigue); // Find first state with fatigue > new_fatigue
// Iterate through states with fatigue > new_fatigue
for(auto it = it_upper; it != dist[u].end(); ++it) {
// If time is also >= new_time, it's dominated
if (it->second >= new_time) {
fatigues_to_remove.push_back(it->first);
}
}
// Perform removals
for (ll f_remove : fatigues_to_remove) {
dist[u].erase(f_remove);
}
}
} // End of check for Action 2 transition
} // End of Dijkstra's main loop
// After the loop finishes (either by finding the optimal solution or exhausting the queue), output the result.
cout << final_min_fatigue << endl;
return 0; // Indicate successful execution
}