7K12 blog

猫でも分かるアルゴリズム解説

AOJ ALDS1_11_B 深さ優先探索

f:id:tkr987:20200612235511p:plain

f:id:tkr987:20200612235519p:plain

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4573439

  • 問題設定が長いので見落としがないよう注意
  • 最短距離(最短到達時間)で更新するとき、更新済み頂点を continue するのを忘れずに書く

f:id:tkr987:20200612235413p:plain

DFSの基本問題。DFSで木構造の各頂点を処理する時は①から④の位置に書く、と暗記すると良いと思う。今回は①と④の位置に処理を書く。最短到達時間で更新するので、更新済み頂点を永遠に更新しないように if (res[v].first != 0) return; を書くのを忘れないように注意する。このif文を書かないと無限ループする。問題文が長いので見落としやすいが、頂点0から到達できない点が存在する時その点をスタートとしてDFSし直すことにも気をつけて処理を書く。計算量は O(E+V)になる。