結果

問題 No.3116 More and more teleporter
コンテスト
ユーザー よいちなすの
提出日時 2025-04-18 21:47:06
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 2,509 bytes
コンパイル時間 838 ms
コンパイル使用メモリ 73,580 KB
実行使用メモリ 16,072 KB
最終ジャッジ日時 2025-04-18 21:47:16
合計ジャッジ時間 6,483 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other RE * 12 TLE * 1 -- * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

struct Query {
    int type, x, c;
};

struct State {
    int pos, cost;
    bool operator>(const State& other) const {
        return cost > other.cost;
    }
};

int main() {
    int N, Q;
    cin >> N >> Q;
    
    vector<int> teleporters(N + 1, -1);  // テレポーターのコスト。-1は未設置を示す。
    vector<int> cost(N + 1, INT_MAX);    // 最小コストの配列
    priority_queue<State, vector<State>, greater<State>> pq;
    
    // 初期状態: 1番目のマスから開始、コストは0
    cost[1] = 0;
    pq.push({1, 0});
    
    // クエリの処理
    while (Q--) {
        int type, x, c;
        cin >> type;
        
        if (type == 1) {  // クエリ1: マス1からマスxまでの最小コストを出力
            cin >> x;
            vector<int> dist(N + 1, INT_MAX);  // 各マスの最小コストを記録
            dist[1] = 0;  // 1からスタート
            pq.push({1, 0});
            
            // ダイクストラ法で最短コストを計算
            while (!pq.empty()) {
                State current = pq.top();
                pq.pop();
                
                if (current.cost > dist[current.pos]) continue;  // コストがすでに最小ならスキップ
                
                // 隣接マスに移動
                if (current.pos > 1 && dist[current.pos - 1] > current.cost + 1) {
                    dist[current.pos - 1] = current.cost + 1;
                    pq.push({current.pos - 1, dist[current.pos - 1]});
                }
                if (current.pos < N && dist[current.pos + 1] > current.cost + 1) {
                    dist[current.pos + 1] = current.cost + 1;
                    pq.push({current.pos + 1, dist[current.pos + 1]});
                }
                
                // テレポーターを使う
                if (teleporters[current.pos] != -1 && dist[teleporters[current.pos]] > current.cost + teleporters[current.pos]) {
                    dist[teleporters[current.pos]] = current.cost + teleporters[current.pos];
                    pq.push({teleporters[current.pos], dist[teleporters[current.pos]]});
                }
            }
            cout << dist[x] << endl;
        
        } else if (type == 2) {  // クエリ2: マスxにテレポーターを設置
            cin >> x >> c;
            teleporters[x] = c;
        }
    }

    return 0;
}
0