問題（外部リンク） Save your cats | Aizu Online Judge 実装の概要 問題の条件を言い換えると、「与えられたグラフから閉路が無くなるように辺を取り除く場合、取り除いた辺の長さの総和の最小値はいくらか」ということになります。 そのため、クラスカル…

問題（外部リンク） Road Construction | Aizu Online Judge 実装の概要 条件より首都から各都市への距離が最短である必要があるので単一始点最短路問題として解きます。Nの値が大きい割に辺の数はMダイクストラ法であれば十分間に合います。 今回は距離の計…

問題（外部リンク） Marked Ancestor | Aizu Online Judge 実装の概要 それぞれのノードに自分の親のidを記憶させます。今回の問題では下に向かって探索することはないので子のidは不要です。 あとはループで親を次々と巡りながらマークされたノードを探しま…

問題（外部リンク） Kakezan | Aizu Online Judge 実装の概要 任意の桁で区切りを入れて計算する処理は記述を簡単にするためにあえて文字列のまま処理をしてみました。実行時間に不安はありましたが無事に制限時間内に実行が終了しました。 今回の問題では「…