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

srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

yukicoder No.160 最短経路のうち辞書順最小

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

ARC 035 C - アットコーダー王国の交通事情

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

ABC 022 C - Blue Bird

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

ABC 016 C - 友達の友達

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