結果
| 問題 |
No.2366 登校
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:12:02 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 9,359 bytes |
| コンパイル時間 | 1,153 ms |
| コンパイル使用メモリ | 113,924 KB |
| 実行使用メモリ | 298,896 KB |
| 最終ジャッジ日時 | 2025-05-14 13:13:39 |
| 合計ジャッジ時間 | 6,587 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 10 TLE * 1 -- * 14 |
ソースコード
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <map>
#include <functional> // Required for std::greater
using namespace std;
// Use long long for time and fatigue values, as they can be large or negative.
typedef long long ll;
// Using pair to store {fatigue, time}.
// std::pair comparison is lexicographical by default: compares first element, then second if first are equal.
// This naturally prioritizes minimum fatigue, then minimum time.
using StateInfo = pair<ll, ll>;
// Define a large constant to represent infinity. Must be large enough to avoid overflow
// when adding costs but greater than any possible finite path cost.
// Max fatigue/time change could be roughly NM * max(C_i or D_i) approx 6400 * 10^9 = 6.4 * 10^12.
// 4e18 (4 * 10^18) is safely within the range of signed 64-bit integers and large enough.
const ll INF = 4e18;
// Define the state key for the distance map. It uniquely identifies a state by
// the number of rewinds used (k) and the location (row r, column c).
// Using pair<int, pair<int, int>> format: {k, {r, c}}.
using StateKey = pair<int, pair<int, int>>;
// Structure to represent a state in the priority queue.
// Contains the StateInfo {fatigue, time} and the StateKey {k, {r, c}}.
struct PQState {
StateInfo info; // {fatigue, time}
StateKey key; // {k, {r, c}}
// Custom comparator for the priority queue to make it a min-heap based on StateInfo.
// `std::priority_queue` by default is a max-heap. Using `std::greater` makes it a min-heap.
// We want to extract the state with the minimum fatigue first. If fatigue levels are equal,
// extract the one with minimum time. This matches the lexicographical comparison of `std::pair`.
bool operator>(const PQState& other) const {
// This defines the order for the min-heap. `a > b` means `a` has lower priority than `b`.
// Check fatigue first.
if (info.first != other.info.first) {
return info.first > other.info.first; // Higher fatigue means lower priority
}
// If fatigue is equal, check time.
return info.second > other.info.second; // Higher time means lower priority
}
};
// Global variables for grid dimensions, number of mysterious squares, and time limit.
int N, M, K;
ll T_limit; // Target time limit
// Map to store mysterious squares data: key {r, c}, value {C, D}
map<pair<int, int>, pair<ll, ll>> mysterious_squares;
// Deltas for moving to adjacent squares: Up, Down, Left, Right
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};
int main() {
// Use faster I/O operations
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// Read input values
cin >> N >> M >> K >> T_limit;
// Read mysterious square data
for (int i = 0; i < K; ++i) {
int r, c;
ll C, D;
cin >> r >> c >> C >> D;
// Input coordinates are 1-based
mysterious_squares[{r, c}] = {C, D};
}
// Set maximum number of rewinds to consider. Based on the pigeonhole principle argument:
// If an optimal path uses more than NM rewinds, it must contain a cycle. Analysis shows
// we can potentially limit the number of "base" rewinds to NM.
int max_k = N * M;
// Use std::map to store the minimum {fatigue, time} found so far for each state {k, {r, c}}.
// This is more memory-efficient than a dense 3D array if many states are unreachable.
map<StateKey, StateInfo> dist;
// Priority queue for Dijkstra's algorithm. Stores PQState objects. Uses the custom comparator `operator>`.
priority_queue<PQState, vector<PQState>, greater<PQState>> pq;
// Initial state: At square (1, 1), 0 rewinds used, fatigue 0, time 0.
StateKey start_key = {0, {1, 1}};
dist[start_key] = {0, 0}; // Record distance to start state
pq.push({{0, 0}, start_key}); // Push the start state into the priority queue
// Variable to track the minimum fatigue found for reaching the goal (N, M) within the time limit T_limit.
ll min_fatigue_at_goal = INF;
// Main loop of Dijkstra's algorithm
while (!pq.empty()) {
// Extract the state with the lowest priority {fatigue, time} from the priority queue.
PQState current = pq.top();
pq.pop();
StateInfo current_info = current.info; // {fatigue, time} of the current state
StateKey current_key = current.key; // {k, {r, c}} of the current state
ll f = current_info.first; // current fatigue
ll t = current_info.second; // current time
int k = current_key.first; // current number of rewinds
int r = current_key.second.first; // current row
int c = current_key.second.second;// current column
// Check if the extracted state is outdated. This happens if we've already found a
// better path to this state {k, r, c} since this state was pushed into the PQ.
// We compare the extracted state's info `current_info` with the stored info `dist[current_key]`.
// If `current_info` is lexicographically greater, it means it's worse (higher fatigue or same fatigue but higher time).
auto it = dist.find(current_key);
// If the key isn't in dist map (should not happen with this logic, but safe check) or info is worse than stored
if (it == dist.end() || current_info > it->second) {
continue; // Skip processing this outdated state
}
// Explore Move actions to adjacent squares
for (int i = 0; i < 4; ++i) {
int nr = r + dr[i]; // Calculate neighbor row
int nc = c + dc[i]; // Calculate neighbor column
// Check if the neighbor coordinates are within the grid boundaries [1..N, 1..M]
if (nr >= 1 && nr <= N && nc >= 1 && nc <= M) {
// Move action: fatigue 'f' remains unchanged, time 't' increases by 1.
StateInfo next_info = {f, t + 1};
// Number of rewinds 'k' also remains unchanged.
StateKey next_key = {k, {nr, nc}};
// Check if the path through the current state to the neighbor state {k, nr, nc}
// is better (lexicographically smaller {fatigue, time}) than any path found so far.
auto it_next = dist.find(next_key);
if (it_next == dist.end() || next_info < it_next->second) {
// If this path is better or if the neighbor state hasn't been reached before,
// update the distance map and push the new state into the priority queue.
dist[next_key] = next_info;
pq.push({next_info, next_key});
}
}
}
// Explore Rewind action if the current square (r, c) is a mysterious square
if (mysterious_squares.count({r, c})) {
// Check if we are within the limit for the number of rewinds 'k'.
if (k + 1 <= max_k) {
// Retrieve the rewind parameters C (time rewind amount) and D (fatigue cost) for this square.
pair<ll, ll> rewind_params = mysterious_squares.at({r, c});
ll C = rewind_params.first;
ll D = rewind_params.second;
// Calculate the state after rewind:
// Fatigue increases by D.
// Time changes by (1 - C). This accounts for the time rewind by C and the 1 second wait period.
StateInfo next_info = {f + D, t + (1 - C)};
// The number of rewinds increases by 1. The location (r, c) remains the same.
StateKey next_key = {k + 1, {r, c}};
// Check if this path to state {k+1, r, c} is better than any path found so far.
auto it_next = dist.find(next_key);
if (it_next == dist.end() || next_info < it_next->second) {
// If better or first time reaching, update distance map and push state to PQ.
dist[next_key] = next_info;
pq.push({next_info, next_key});
}
}
}
}
// After Dijkstra's algorithm finishes, examine all reachable states corresponding to the goal square (N, M)
// for all possible number of rewinds k from 0 to max_k.
for (int k = 0; k <= max_k; ++k) {
StateKey goal_key = {k, {N, M}};
auto it = dist.find(goal_key);
// Check if the state {k, N, M} was reachable
if (it != dist.end()) {
StateInfo goal_info = it->second; // Get the {fatigue, time} for this state
// Check if the time 'goal_info.second' meets the time limit T_limit
if (goal_info.second <= T_limit) {
// If it does, update the overall minimum fatigue found.
min_fatigue_at_goal = min(min_fatigue_at_goal, goal_info.first);
}
}
}
// Output the final result.
if (min_fatigue_at_goal == INF) {
// If min_fatigue_at_goal is still INF, it means the goal was not reachable within the time limit.
cout << -1 << endl;
} else {
// Otherwise, output the minimum fatigue found.
cout << min_fatigue_at_goal << endl;
}
return 0; // Indicate successful execution
}