問題 問題概要 最短経路を復元する。経路復元。 解法 ダイクストラでやる。経路復元は蟻本を参照。 気をつけることは、s->gの最短経路を求めるのではなく、今回は無向グラフであることを利用して、g->sへの最短経路を求め、そのついでにもとめられるpreを利…

問題 問題概要 省略 解法 まず、ワーシャルフロイドで、任意の２点間の最短距離を計算しておく。そのあとは、辺が一つ追加されるだけなので、追加される辺が、x-yであれば、任意の２点間の最短距離は、i -> j = i -> x -> y -> j = i -> y -> x -> j のなか…

問題 問題概要 省略 解法 ダイクストラでやろうと思うと、閉路の最短距離を出すのは普通にやったらできない。求めるのは0から初めて、0に戻るような閉路で最短距離。そのような経路は、0 -> u -> v -> 0 ものである。同じ道を２度通ることはできないので、u…

問題 問題概要 省略 解法 dfsで友達の友達を求めることにした。この時に、dfsの引き数として、現在の頂点と、前回の頂点、探索回数、スタート時点の頂点を持つことにした。前回の頂点は元の頂点に戻るのを禁止しするため。スタート時点を保持しておくのは、…