AtCoder ABC051-D Candidates of No Shortest Paths 〜すいかの精進旅日記〜
まったりトークコーナー
これから400点問題を埋めていくことが増えていきそうなので、復習なども兼ねて備忘録としてブログを書くことにしました。
ただ備忘録って書いてる人は時々見かける気がするので、ちょっとカッコつけて旅日記っていう言葉を使ってみました。すぐ周りと違うことをしたがる凡人の極みですね。（？）
それから当方茶色なので、間違いなどがあれば優しく指摘してくれると嬉しいよ！！＞＜
（ただ参考にしてくださった方には本当に申し訳ないので、話半分ぐらいでみてくれるといいかもしれません！）
当然ネタバレなどを含むので、みたくない人は撤退を推奨です＞＜
問題
解法
はっきり言って、ほぼみなさま頼りだったので、参考になったサイトなどを掲載しておきます。
いつものごとくけんちょんさんも登場です。
とってもわかりやすかったです！！
自分の書いたコードも最終的にはけんちょんさんのコードをほぼ写経しました（）
ワーシャルフロイド法については以下のサイトにお世話になりました。とても参考になったので、ワーシャルフロイド法がまだ不安って人は是非みてみると良いと思います。
（みなさまありがとうございました！）
AtCoder Beginner Contest 073 解説放送 - YouTube
解説ACとかになると自分なりの言葉をある程度用意できても、中々まだ人の言葉を使ってる感覚にもなるので罪悪感もありますね。ただ、こう言った記事を書く以上なるべく自分の言葉で頑張っていこうと思います。（もしも頼り過ぎた言葉になってたらごめんなさい！）
それでは、あくまで備忘録で解説ってわけでもないので、簡潔にいきます。（ちょっとは誰かがこの問題で躓いた時に助けになれたらなって気持ちはあります。）
連結グラフなので連結グラフを考えます。（それはそう）
グラフなので、DFSやUnion Find木なども考えたくなりますが、木じゃないことや最短経路を考える、N <= 100という条件からダイクストラ法やワーシャルフロイド法を使いたいような気持ちになると多分きっと嬉しいです。
ここで「どの異なる２頂点間の、どの最短経路にも含まれない辺の数」を満たす条件を考えます。まず最短経路になる可能性のあるルートを考えると、直接頂点aから頂点bへ行くルートと、頂点aから頂点cなどへ行ってから頂点bへ行く迂回ルートがあります。この時頂点aからbへ直接行くルートが最短経路だった場合、当然辺abは最短経路に含まれます。しかし、迂回ルートが最短だとすると、辺abが最短経路ではなくなるのでこれが最短経路にも含まれない辺になることがわかりますね！（どちらとも最短経路のケースもあることに注意！）また、どの異なる２頂点間でも〜とありますが、頂点a-b間が最短じゃない時点で、他に最短で良いルートがあるということなので気にしなくても良いです。
あとは、ワーシャルフロイドなどで各頂点の最短距離を求めて、その最短距離よりも距離がある辺を調べていけば良さそうです。
そしてほぼ写経によって書き上げられたコードがこちらです！（ちなみにPythonです）
おまけ（すいかの失敗話）
実は、初めはワーシャルフロイドなんてすっかり忘れててDFSで取り組んでました。
以下がそのコードになります。初めはO(N^3)ぐらいで各点からのDFSをして、その距離をうまく保存更新（visitedをvisited[N][N][2]で持つとかを考えた）、比較して解法に書いた方法をすればいけそうと思ったのですが、いつの間にかO(N^2)でいけるやろみたいに思ってしまって謎のコードが完成しました。できた時にはダメだと思ったのですが、一応サンプルを通したところ何故か全部通ったので投げてみると5/30ぐらいは進んで少し面白かったです笑
