ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

グラフ理論

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

概要0~N-1のN個の駅があり、駅と駅は路線で結ばれ、それぞれ移動距離が決められている。ある駅Sからある駅Gまでの最短経路を求めよ。 最短経路が複数存在する場合は、その中で辞書順最小のものを出力せよ。N<=200http://yukicoder.me/problems/417

Valentine's Day Round (BestCoder #030) C : The Experience of Love

概要N個の町とN-1本の道がある。町には1~Nまで番号がつけられており、道は2つの町a,bを距離cでつないでいる。ある町から別の町に行くときに通る道のうち、最大の距離を持つ道と最小の距離を持つ道の距離の差を計算する。例えば町1,2,3があり、町1,2間の距離…

ABC #014 D 閉路

概要 問題文はこちら http://abc014.contest.atcoder.jp/tasks/abc014_4n個のノードとn-1本のエッジからなる無向グラフがある。 そこに1本エッジを増やして閉路を作った時の閉路の長さを求めよ。・n ・クエリがたくさん解法 エッジを張る2頂点間の距離が分…