🐡

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

2024/12/31に公開

 問題https://atcoder.jp/contests/abc211/tasks/abc211_d

 要約AtCoder国には1からNまでの番号がついたN個の都市がある。
1からMまでの番号がついたM個の道路がある。
道路iは都市AiとBiを双方向に結んでおり、通過するのに1時間かかる。
都市1から都市Nまでの最短経路の数を求める。
答えは(10^9 + 7)で割った余りを出力する。
N: 都市の数
M: 道路の数
Ai, Bi: 各道路iが結ぶ2つの都市の番号（1 ≤ i ≤ M）

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

 アプローチグラフの最短経路を求めつつ、その経路の数も同時にカウントする

 解法手順入力を受け取り、グラフを隣接リストとして表現する。
各都市に対して、最短距離を保存する配列と、その都市までの最短経路の数を保存する配列を用意する。
幅優先探索（BFS）を使用して、都市1から各都市への最短距離を求める。
BFSの過程で、各都市への最短経路の数も同時に計算する。
ある都市への新しい最短経路が見つかった場合、その都市への経路数を更新する。
既知の最短経路と同じ長さの経路が見つかった場合、その都市への経路数に新しい経路数を加算する。
経路数の計算では、常に10^9+7で割った余りを保持する。
最終的に、都市Nへの最短経路の数（10^9+7で割った余り）を出力する。

 ACコードac.py
import sys
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(10**9)  # 再帰の深さ制限を設定

def io_func():
    # 入力を受け取る
    n, m = map(int, input().split())  # 都市の数nと道路の数mを入力
    graph = defaultdict(list)  # グラフを隣接リストとして表現
    for _ in range(m):
        a, b = map(int, input().split())  # 道路の情報を入力
        graph[a].append(b)  # 無向グラフなので両方向に追加
        graph[b].append(a)
    return n, m, graph

def solve(n, m, graph):
    MOD = 10**9 + 7  # 余りを取る数
    distances = [float('inf')] * (n + 1)  # 各都市への最短距離を保存
    path_counts = [0] * (n + 1)  # 各都市への最短経路の数を保存

    queue = deque()
    start = 1  # 始点は都市1
    distances[start] = 0
    path_counts[start] = 1
    queue.append(start)

    while queue:
        current = queue.popleft()
        for neighbor in graph[current]:
            if distances[neighbor] > distances[current] + 1:
                # 新しい最短経路が見つかった場合
                distances[neighbor] = distances[current] + 1
                path_counts[neighbor] = path_counts[current]
                queue.append(neighbor)
            elif distances[neighbor] == distances[current] + 1:
                # 既知の最短経路と同じ長さの経路が見つかった場合
                path_counts[neighbor] += path_counts[current]
                path_counts[neighbor] %= MOD

    return path_counts[n]  # 都市Nへの最短経路の数を返す

# メイン処理
n, m, graph = io_func()  # 入力を受け取る
result = solve(n, m, graph)  # 問題を解く
print(result)  # 結果を出力

###
# - n: 都市の数
# - m: 道路の数
# - graph: 都市間の接続関係を表す隣接リスト
# - distances: 各都市への最短距離を保存するリスト
# - path_counts: 各都市への最短経路の数を保存するリスト
# - queue: BFSで使用するキュー
# - MOD: 余りを取る数（10^9 + 7）

# 1. 入力処理（io_func関数）
#    - 都市の数nと道路の数mを入力
#    - m本の道路の情報を入力し、隣接リストとしてグラフを構築
# 2. メイン処理（solve関数）
#    - 最短距離と経路数を保存するリストを初期化
#    - 幅優先探索（BFS）を実行
#      - 始点（都市1）から探索を開始
#      - 各都市を訪れる際に、最短距離と経路数を更新
#      - 新しい最短経路が見つかった場合、その都市の経路数を更新
#      - 既知の最短経路と同じ長さの経路が見つかった場合、経路数を加算
#    - 経路数の計算では常にMODで割った余りを保持
#    - 最終的に都市Nへの最短経路の数を返す
# 3. 結果出力
#    - solve関数の結果を出力```

問題

要約

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

アプローチ

解法手順

ACコード

Discussion