Flying Trip [第七回 アルゴリズム実技検定 K]

https://atcoder.jp/contests/past202107-open/tasks/past202107_k

前提知識

• ダイクストラ

解説

今回の問題は無向グラフが与えられて頂点1から頂点Nへの最短距離で、かつ、満足度が最高のものを選択することが目的。
特に前半の「無向グラフが与えられて頂点1から頂点Nへの最短距離」という所でだいぶダイクストラかなという感じがする。
今回の解説はダイクストラが分かっていることを前提として話す。
もし、わかっていない場合はどこかで勉強してから以降読み進めてほしい。
ダイクストラを学んで、手になじんできた4問目くらいに取り組むといい問題じゃないかな？

今回のダイクストラは？

今回のダイクストラでは、一般的なダイクストラに距離以外の要素を追加して、そっちも最適化するという方針になる。
一般に、ダイクストラを進めるうえで、処理済みかを示すvis配列みたいなものと、現在の最適解を保持するopt配列みたいなものを用意する。
この最適解は

opt[cu] := 頂点cuに至るまでの経路での最短距離

のように定義することが多い。
今回では最短距離が最小で、かつ、満足度が最高のものを求めていきたいので、

opt[cu] := 頂点cuに至るまでの経路での{最短距離, その中での最大満足度}

という風にpairで定義することにする。
こうすることで何が変わるかというと、以前はopt[cu]'＜opt[cu]みたいな単純な大小比較で済んだものが、

• opt[cu].first'＜opt[cu].firstだったら、最短経路も満足度も更新
• opt[cu].first'＝opt[cu].firstだったら、満足度だけ大きい方で更新

みたいにちょっと工夫した比較で更新していく。
でも、普通のダイクストラに比べて定義と更新部分を変えるだけでいいので、慣れればすんなりかける。

int N, M, A[101010];
vector<pair<int, int>> E[101010];
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
ll vis[101010];
pair<ll, ll> opt[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, M) {
        int a, b, t; cin >> a >> b >> t;
        a--; b--;
        E[a].push_back({ b, t });
        E[b].push_back({ a, t });
    }

    rep(i, 0, N) opt[i] = { infl, 0 };
    rep(i, 0, N) vis[i] = 0;

    min_priority_queue<pair<ll, int>> que;

    opt[0] = { 0, A[0] };
    que.push({ 0, 0 });

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

        ll cst = q.first;
        int cu = q.second;

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

        fore(p, E[cu]) {
            ll cst2 = cst + p.second;
            int to = p.first;

            if (cst2 < opt[to].first) {
                opt[to] = { cst2, opt[cu].second + A[to] };
                que.push({ cst2, to });
            }
            else if (cst2 == opt[to].first) {
                chmax(opt[to].second, opt[cu].second + A[to]);
            }
        }
    }

    cout << opt[N - 1].second << endl;
}