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))
