2012-08-31から1日間の記事一覧
問題リンク Mr. Rito Post Office 解法 ワーシャルフロイドで下ごしらえしてからDPで解きました。 まず、陸路のみでの移動、海路のみでの移動それぞれについて全頂点間最短距離をワーシャルフロイドで求めます。 次に、以下のようなDPを考えます。 dp[i][j]:…
問題リンク Mr. Rito Post Office 解法 ワーシャルフロイドで下ごしらえしてからDPで解きました。 まず、陸路のみでの移動、海路のみでの移動それぞれについて全頂点間最短距離をワーシャルフロイドで求めます。 次に、以下のようなDPを考えます。 dp[i][j]:…