読者です 読者をやめる 読者になる 読者になる

ABC 22-C Blue bird

重りつきのグラフが与えられ、スタート地点から出発しスタート地点へ戻ってくる最短の道のりを答える問題。 C: Blue Bird - AtCoder Beginner Contest 022 | AtCoder

最初はダイクストラに通った道を記憶させ、それを通らないようにするんだと思って実装するも、探索する量が多くなりTLE。そこから考えてもわからなかったので、解説をみてちょっと実装。TLE。結局、最後まで解説をみてACできました。

グラフだし、最小パスを求めるからできると思いましたが、出来ませんでした。悔しい。この問題から一般的な知識を得るとしたら何になるんでしょうか。

  • 閉路とは、どの点をとっても2つの点で結ばれてる。
  • 最小の閉路の中で同じ点を2度訪れることはない

こんな感じですかね。一つ目がわかってれば、始まりの点から繋がってる点を順繰りに試して短いものをキープしてけばいいんだという発送に繋がりそうです。C問題も自力で解ける問題がなくなってきました。これからは、2,3日かけて考えてわからなかったら解説をみるという流れになりそうです。