AIで解説 AtCoder攻略　最短経路

最短経路ページの位置づけ

項目	内容
必修度	重要
学習目安	標準〜発展
前提	グラフ・deque・heapq
対象問題	92問（推定値あり92問、未算出0問）

この記事のdifficulty区分は、問題を解く順番を決めるための目安です。AtCoderの公式なA〜F区分ではなく、取得できたdifficulty推定値を次の範囲に分けています。

学習目安	difficulty推定値	問題数
入門	difficulty < 0	2
標準	0〜799	18
標準〜発展	800〜1199	22
発展	1200以上	50
未算出	—	0

頂点やマスを状態として、距離の小さい順に探索します。辺の重みが一様ならBFS、非負の重みがあればDijkstraを選びます。

問題ごとの細かな実装は異なりますが、最初に確認する条件は共通しています。

最短経路の見分け方

最小移動回数や最小コストを求める
一度確定した距離を再利用できる
重みの有無で探索方法を切り替えられる

最短経路の実装前チェック

状態と辺の重みを定義する
BFS・0-1 BFS・Dijkstraのどれかを選ぶ
古いヒープ要素を取り出したときに捨てる

先に確認する文法・ライブラリ

まずは必須Python文法で、入力・配列・条件分岐・ループなどの基本を確認してください。問題に合わせたキュー、ヒープ、二分探索などの選び方は標準ライブラリ・定石にまとめています。

代表問題で実装を確認する

最初の一問として、ABC308 D G. Snuke Maze（公式解説）を解きます。文字列snukeを繰り返しながら進めるマスだけをBFSで調べます。距離の順に探索するので、初めてゴールへ着いた経路が最短です。

from collections import deque

H, W = map(int, input().split())
grid = [input().strip() for _ in range(H)]
pattern = 'snuke'
queue = deque([(0, 0, 0)])
seen = {(0, 0)}
answer = False

while queue:
    r, c, distance = queue.popleft()
    if (r, c) == (H - 1, W - 1):
        answer = True
        break
    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nr, nc = r + dr, c + dc
        if not (0 <= nr < H and 0 <= nc < W):
            continue
        if (nr, nc) in seen or grid[nr][nc] != pattern[(distance + 1) % 5]:
            continue
        seen.add((nr, nc))
        queue.append((nr, nc, distance + 1))

print('Yes' if answer else 'No')

各マスを高々1回訪れるO(HW)時間・O(HW)メモリです。

最短経路の学ぶ順番

このページでは全件を一度に並べず、difficultyの推定値を目安に代表問題を段階分けしています。難易度が未算出の問題は、制約と出題意図を先に確認します。

まず解く

問題	公式解説	出題意図	difficulty
ABC470 B Monocolor	公式解説	Flood-fill monochrome regions and test corridor connectivity.	-649
ABC270 B Hammer	公式解説	目的地への直線経路上に壁がある場合だけハンマー取得の迂回距離を比較する。	-131
ABC370 C Word Ladder	公式解説	Official editorial intent is classified as word ladder edit path.	176
ABC383 B Humidifier 2	公式解説	加湿器の到達可能範囲をグリッド上の距離・エネルギー状態で探索する。	246
ABC453 C Sneaking Glances	公式解説	Propagate line-of-sight glances through the grid.	333

次に解く

問題	公式解説	出題意図	difficulty
ABC450 C Puddles	公式解説	Flood-fill puddles in the grid and count their connected areas.	362
ABC405 D G. Escape Route	公式解説	公式Editorialの方針を grid bfs escape として整理する。	471
ABC308 D G. Snuke Maze	公式解説	Run BFS from S while matching the repeating Snuke directions.	619
ABC309 D G. Add One Edge	公式解説	Run BFS from vertex 1 and from the final vertex inside the two components, then maximize dist1[u]+1+distN[v].	621
ABC204 C Tour	公式解説	Run a graph search from every city and count all reachable ordered pairs.	629

挑戦問題

問題	公式解説	出題意図	difficulty
ABC436 D G. Teleport Maze	公式解説	Run shortest-path BFS while treating each available teleport as an additional transition.	633
ABC362 D G. Shortest Path 3	公式解説	Official editorial intent is classified as node cost dijkstra.	634
ABC406 D G. Garbage Removal	公式解説	公式Editorialの方針を grid garbage bfs として整理する。	694
ABC420 D G. Toggle Maze	公式解説	公式Editorialの方針を toggle maze bfs として整理する。	699
ABC441 D G. Paid Walk	公式解説	Run Dijkstra on the paid-walk graph and return the shortest fare.	732