square869120Contest #1-C お金の街 (The Money Town)
躓いたのでメモ
問題概要
各頂点にお金が割り振られた無向グラフが与えられる
始点は自由で、より多くのお金を獲得したい、ただし同じ頂点は1回しか通れない
考察・解法
各頂点からそれぞれDFSして最大値更新すればOK~~~と考えたが、入力例1で不可能と判断
入力例1は以下の様なグラフになる
隣接リストで辺を管理する場合、頂点1の次は頂点2に到達してしまい、頂点3には到達できず最大値を取れなくなってしまう
なので、ある頂点から再帰的にDFSを行うとき、新しく到達した頂点の訪問の有無を記録する配列をfalseにしてあげることで1つの頂点からの最大値を取りうる経路の探索が可能となる
説明下手くそすぎるので図にかいた
入力例1の場合を考える
・経路例1
・経路例2
辺自体にコストがあるわけではなく、頂点自体にコスト（しかも大きい方が良しとされる）ので単純なDFSをしてしまうとある頂点Aから別のある頂点までの経路は最短経路の更新がなされないため、1通りとなってしまい題意通りの答えを出力できない
なので、以下の様にする
