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

らての精進日記

修行をします

aoj2200:Mr.Rito Post Office

解法

陸路のみでの全点対最短経路問題を解いておく。
同様に、海路のみでの全点対最短経路問題も解いておく。

陸路での頂点vから頂点uへの最短経路をL[v][u]とする。同様に海路ではS[v][u]とする。

これらは、ワーシャルフロイド法を使えばO(N^3)なので間に合う。

dp[i][j]:=i番目の配達まで完了して、船がj番目のところにあるときの最小コスト、として、配るdpをする。

i番目の配達目標をvとして、i+1番目の配達目標をuとすると、(i=0のときはv=1とする)
dp[i+1][k]=min(dp[i+1][k],dp[i][j]+L[v][j]+S[j][k]+L[k][u]) (0<=k< N) という風に配るとok。

全体で、O(N^2(N+R))

コード