【競技プログラミング】AtCoder Beginner Contest 340_D問題

問題

要約

1. ゲームには1からNまでの番号がついたN個のステージがある。
2. 最初はステージ1のみが遊べる。
3. 各ステージi (1 ≤ i ≤ N-1) では2つの選択肢がある：
   a. Ai秒かけてクリアし、ステージi+1を解放する。
   b. Bi秒かけてクリアし、ステージXiを解放する。
4. ステージNを遊べるようになるまでの最短時間を求める。

変数情報：

• N: 全ステージ数
• Ai: ステージiをクリアしてi+1を解放するのにかかる時間
• Bi: ステージiをクリアしてXiを解放するのにかかる時間
• Xi: ステージiをBiの方法でクリアした場合に解放されるステージ番号

既存投稿一覧ページへのリンク

一覧ページ

アプローチ

グラフ探索問題として捉える。
各ステージをノードとし、ステージ間の移動を重み付きエッジとして表現する。
ステージ1（始点）からステージN（終点）までの最短経路を求めることで、最短時間を算出する。

解法手順

1. 入力からステージ数Nを読み取る。

2. グラフを表現するためのデータ構造を初期化する。各ステージ（ノード）から移動可能な次のステージ（ノード）へのエッジとその重み（時間）を格納する。

3. N-1回のループで各ステージの情報を読み取り、グラフを構築する：

   • Ai秒でステージi+1に移動するエッジを追加する。
   • Bi秒でステージXiに移動するエッジを追加する（ただし、Xi ≤ Nの場合のみ）。

4. ダイクストラのアルゴリズムを実装し、ステージ1からの最短経路を求める：

   • 優先度付きキューを使用して、現在の最短距離が最小のノードを効率的に選択する。
   • 各ノードまでの最短距離を更新しながら、グラフを探索する。

5. ダイクストラのアルゴリズムによって得られた、ステージNまでの最短距離（時間）を出力する。

ACコード

ac.py

import heapq  # 優先度付きキューを使用するためにheapqをインポート

# ダイクストラのアルゴリズムを実装する関数
def dijkstra(graph, start):
    # スタート地点から各ノードまでの距離を無限大で初期化
    distance = [float('inf')] * len(graph)
    distance[start] = 0  # スタート地点の距離は0
    queue = [(0, start)]  # (距離, ノード)のタプルをキューに入れる

    while queue:
        # 最短距離のノードを取り出す
        dist, current = heapq.heappop(queue)
        if distance[current] < dist:
            continue

        # 現在のノードから到達可能なノードについて距離を更新
        for next_node, weight in graph[current]:
            new_dist = dist + weight
            if new_dist < distance[next_node]:
                distance[next_node] = new_dist
                heapq.heappush(queue, (new_dist, next_node))

    return distance

# メイン処理
def solve(graph):
    # 4. ダイクストラのアルゴリズムを実行し、ステージ1からの最短経路を求める
    start = 0  # スタート地点（ステージ1）
    distance = dijkstra(graph, start)

    # 5. ステージNまでの最短距離（時間）を出力する
    print(distance[N-1])

if __name__=="__main__":
    # 1. 入力からステージ数Nを読み取る
    N = int(input())  # ステージの数

    # 2. グラフを表現するためのデータ構造を初期化する
    graph = [[] for _ in range(N)]

    # 3. N-1回のループで各ステージの情報を読み取り、グラフを構築する
    for i in range(N-1):
        A, B, X = map(int, input().split())
        graph[i].append((i+1, A))  # 行動Aによるエッジを追加
        if X-1 < N:
            graph[i].append((X-1, B))  # 行動Bによるエッジを追加（Xi ≤ Nの場合のみ）
    
    solve(graph)

机上トレース