小橋　解説

問題 : ABC211-D

https://scrapbox.io/files/610e7ed7935d5a001e07ca19.png

・最短経路を1つ求めろ　-->　DFS ? BFS ?

・最短経路の数を求めろ -->　全部の経路見ないといけない？　-->　BFS ？

DFS --> 再帰を使って実装

BFS --> キューを使って実装

〜〜実行時間の問題〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜

DFSやBFSの実行時間　ーー＞　O(N+M)　※N=ノード(町)の数、M=辺(道)の数

今回の問題は2<N<2 * 10^5、0<M<2 * 10^5　なので　合計O(2 * 10^6) -->　OK

〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜

幅優先のいいところ

--> DFSは後からその街へ行くための新しい最短経路が見つかる可能性がある

--> BFSは後からより早い経路が見つかることはない、前までの最短経路と同じ速さでいける経路しか見つからない

〜〜コード〜〜

code:python

N, M = map(int, input().split())

roads = []

for i in range(M):

roads.append(list(map(int, input().split())))

# ①　初めにどこからどこへ行けるかの配列(graph)を作成する

graph = []

for _ in range(N):

graph.append([])

# どこからどこにいけるかの配列(graph)を作成

for i in roads:

#　②　幅優先探索を使ってとく

for v in que:

que.append(vv) # 次に見る町をクエリに格納

入力例１に対する動作の説明

参考：