【AtCoder】ABC 340 D - Super Takahashi Bros. | 茶コーダーが解くAtCoder

atcoder.jp

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 784

問題概要

の番号が付いた 個のステージがあり、現在はステージ1のみが遊べる。各ステージ が遊べるとき、ステージ では次の2つの行動のどちらかを行うことができる。各ステージをクリアするためにかかる時間以外は無視できるとき、ステージ を遊べるようになるのは最短で何秒後か。

• 行動 :

1. 秒かけてステージ をクリアする。結果、ステージ が遊べるようになる。
2. 秒かけてステージ をクリアする。結果、ステージ が遊べるようになる。

制約

• 入力はすべて整数。
• 
• 
• 

考察

頂点をステージ、辺の重みをステージが遊べるようになるまでの時間として、サンプルケース1の様子をグラフで図示してみると以下のようになる。太線矢印の遷移が最短となる。

一般化して考えると、求めたいのは頂点1から頂点 までの最短経路ということになる。重み付き有向グラフにおいてある頂点からの最短経路を求めるときに使えるアルゴリズムは、「ダイクストラ (Dijkstra) 法」だ。

ダイクストラ法は、「ある1つの始点から各点への最短経路を求めるアルゴリズム」である。辺の重みが負になるものがある場合は使えないが、今回は時間が辺の重みになるため負の辺は存在しない。

ダイクストラ法を使えばよいということが分かれば実装自体はシンプルで、 から までの 個の各頂点からそれぞれ2本の辺を張っていけばよい。

コード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define rep(i, start, end) for (ll i = (start); i < (ll)(end); i++)

// ======================================== //

struct Edge
{
    ll to;
    ll cost;
};

using Graph = vector<vector<Edge>>;
using Pair = pair<ll, ll>;

void Dijkstra(const Graph &graph, vector<ll> &distances, ll startIndex)
{
    priority_queue<Pair, vector<Pair>, greater<Pair>> p_queue;
    p_queue.emplace((distances[startIndex] = 0), startIndex);

    while (!p_queue.empty())
    {
        const ll distance = p_queue.top().first;
        const ll from = p_queue.top().second;
        p_queue.pop();

        if (distances[from] < distance)
            continue;

        for (const auto &edge : graph[from])
        {
            const ll new_distance = (distances[from] + edge.cost);

            if (new_distance < distances[edge.to])
                p_queue.emplace((distances[edge.to] = new_distance), edge.to);
        }
    }
}

int main()
{
    int N;
    cin >> N;

    Graph G(200020);
    rep(i, 1, N)
    {
        ll A, B, X;
        cin >> A >> B >> X;
        G[i].push_back(Edge{i + 1, A});
        G[i].push_back(Edge{X, B});
    }

    vector<ll> dist(N + 1, INFL);
    Dijkstra(G, dist, 1);

    cout << dist[N] << endl;
}

atcoder.jp

実装時間: 40分

最初に動的計画法で実装してしまい、サンプルケース2で落とされてしまった。時系列順の探索はダイクストラ法という認識で良いのかもしれない。