観光計画 [Kotamanegi Online Judge No.73]

https://kotamanegi.com/Problems/view/index.php?page=73

前提知識

• ダイクストラ

考察過程

1. 観光できるホテルは「任意の快適度dのホテルが距離d以内に存在する」ことである
2. 思いつく解法が、全ての頂点から全てのホテルをチェックする解法だがO(NK)で駄目
3. 全てのホテルを扱わない方法は無いか？
4. ここで観光できるホテルの条件を「任意の快適度d,距離eのホテルのうち、0≦d-eであるものが存在する」ことと言い換える
5. こうすると、d-eが最適が最適なホテルだけ保持していけばいいのでは？と推測される
6. 重み付き無向グラフで使えるダイクストラっぽい感じにやれそう
7. 解けた

解法

https://kotamanegi.com/Submission/view/index.php?SubmissionID=1791

ダイクストラの要領で解く。
各頂点について、全てのホテルの中で「快適度-距離」の最大値を求めながら、観光できるかを数えていく。
priority_queueで（快適度-距離, 頂点）を持って、更新していく。
通常のダイクストラと異なり、快適度-距離が大きい方から行っていくことで最大値を求めていくことができる。
　
最初はpriority_queueに（ホテルの快適度, ホテルの頂点）を入れておく。
priority_queueから取り出して、遷移させると、距離分だけ快適度が減るので、減らして遷移先を入れる。
この時に、快適度-距離が0以上であることをチェックしておくと、取り出した頂点が観光できる頂点となるので、ans++する。

int N, M, K;
vector<pair<int, int>> E[101010];
int vis[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> K;
    rep(i, 0, M) {
        int a, b, c; cin >> a >> b >> c;
        a--; b--;
        E[a].push_back({ b, c });
        E[b].push_back({ a, c });
    }

    priority_queue<pair<int, int>> que;
    rep(i, 0, K) {
        int h, d; cin >> h >> d;
        h--;
        que.push({ d, h });
    }

    int ans = 0;
    while (!que.empty()) {
        auto q = que.top();
        que.pop();

        int cu = q.second;
        int rest = q.first;

        if (vis[cu]) continue;
        vis[cu] = 1;
        ans++;

        fore(tp, E[cu]) {
            int to = tp.first;
            int cst = tp.second;

            if (vis[to]) continue;
            if (0 <= rest - cst) que.push({ rest - cst, to });
        }
    }

    cout << ans << endl;
}