Tour(ABC204)

c++

Tour

問題

C - Tour
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

提出

Submission #44556617 - AtCoder Beginner Contest 204
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解けた

以下、解法を記載する。

スタート地点を固定して、全探索する。
全探索をDFSで行うと、$O(N+M)$になる。
スタート地点は全部でN個あるので$O(N(N+M))$になる。
この問題では、最大で$N=2000, M=2000$なので、$10^6$くらいの計算量になるので間に合う。
初めはこの制約に気づかなかったため、複雑に考えてしまった。

コメント

タイトルとURLをコピーしました