結果

問題 No.2099 [Cherry Alpha B] Time Machine
ユーザー qwewe
提出日時 2025-05-14 13:14:07
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 4,972 bytes
コンパイル時間 893 ms
コンパイル使用メモリ 91,076 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-05-14 13:15:25
合計ジャッジ時間 4,534 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 TLE * 1 -- * 68
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <queue>
#include <map>

// Define long long type alias for convenience, especially for large numbers
using ll = long long;

// Use a map to store minimum distances (costs) to visited days (states).
// Key: day (represented by long long), Value: minimum cost to reach this day (long long).
// A map is suitable here because the state space (days) can be very large and sparse.
// We only store entries for days that are actually reached.
std::map<ll, ll> dist;

int main() {
    // Faster I/O operations by disabling synchronization with C standard streams
    // and uncoupling cin/cout.
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    ll T; // Target day T. Can be positive or negative.
    std::cin >> T;

    ll X, A; // Action 2: Time machine forward. Costs X, moves +A days.
    std::cin >> X >> A;

    ll Y, B; // Action 3: Time machine backward. Costs Y, moves -B days.
    std::cin >> Y >> B;

    // Priority queue for Dijkstra's algorithm. Stores pairs {cost, day}.
    // The priority queue is implemented as a min-heap using std::greater,
    // so the element with the smallest cost has the highest priority.
    std::priority_queue<std::pair<ll, ll>, std::vector<std::pair<ll, ll>>, std::greater<std::pair<ll, ll>>> pq;

    // Initialize the distance to the starting day (day 0) as 0 cost.
    dist[0] = 0;
    // Push the starting state {cost=0, day=0} into the priority queue.
    pq.push({0, 0});

    // Main loop of Dijkstra's algorithm
    while (!pq.empty()) {
        // Extract the state (pair of cost and day) with the minimum cost from the priority queue.
        std::pair<ll, ll> top = pq.top();
        pq.pop();

        ll cost = top.first;        // Current minimum cost to reach current_day
        ll current_day = top.second; // The day corresponding to this state

        // If the extracted state corresponds to the target day T, we have found the shortest path.
        // Print the minimum cost and exit the program successfully.
        if (current_day == T) {
            std::cout << cost << std::endl;
            return 0;
        }

        // Optimization: If the cost extracted from the priority queue is greater than the already known
        // shortest distance to current_day stored in the map, it means we found a shorter path to this day earlier.
        // This state is outdated, so we skip processing it.
        // It's important to check dist.count(current_day) first to ensure the key exists before accessing dist[current_day].
        // This check prevents accessing a non-existent key which might insert a default value (0 for ll) incorrectly.
        if (dist.count(current_day) && cost > dist[current_day]) {
             continue;
        }
        
        // Explore neighbors (next possible states) based on the three possible actions:

        // Action 1: Wait 1 day.
        ll next_day1 = current_day + 1; // Move to the next day (day + 1)
        ll cost1 = cost + 1;            // The cost increases by 1 (experienced time)
        // Check if next_day1 hasn't been visited yet (!dist.count(next_day1)) or if the new path
        // through current_day offers a shorter cost (cost1 < dist[next_day1]).
        if (!dist.count(next_day1) || cost1 < dist[next_day1]) {
             dist[next_day1] = cost1; // Update or set the minimum distance to next_day1
             pq.push({cost1, next_day1}); // Add the new state {cost1, next_day1} to the priority queue
        }

        // Action 2: Use time machine to travel A days into the future.
        ll next_dayA = current_day + A; // Move A days forward (day + A)
        ll costA = cost + X;            // The cost increases by X
        // Check if this path is shorter than any known path to next_dayA
        if (!dist.count(next_dayA) || costA < dist[next_dayA]) {
             dist[next_dayA] = costA; // Update or set the minimum distance
             pq.push({costA, next_dayA}); // Add the new state to the priority queue
        }

        // Action 3: Use time machine to travel B days into the past.
        ll next_dayB = current_day - B; // Move B days backward (day - B)
        ll costB = cost + Y;            // The cost increases by Y
        // Check if this path is shorter than any known path to next_dayB
         if (!dist.count(next_dayB) || costB < dist[next_dayB]) {
             dist[next_dayB] = costB; // Update or set the minimum distance
             pq.push({costB, next_dayB}); // Add the new state to the priority queue
        }
    }

    // According to the problem statement, it is guaranteed that day T is always reachable.
    // Therefore, the program should always find T and exit via the `return 0;` statement inside the loop.
    // Reaching this point indicates an issue (e.g., T was somehow unreachable, or a bug in the logic).
    return 1; // Return a non-zero value to indicate an error or unexpected termination condition
}
0