AOJ 2200 Mr. Rito Post Office
最短路を求めるんですが、船という要素が問題を複雑にしています。
各点間の最短距離をあらかじめ求めといて、船の位置でDPするだけ!
ワーシャルフロイドとか初めて使ったわw
グラフのサイズ小さいと便利だね!
ちなみに、"リト"ではなく"利藤"です。
#include<cstdio> #include<vector> #include<algorithm> #include<queue> using namespace std; typedef pair<int, int> P; const int INF = 100000000; int dl[201][201], ds[201][201], n, m, dp[1000][201]; int main(){ int x, y, t, r, z, rz; char sl; while(1){ scanf("%d%d",&n,&m); if(n == 0) return 0; for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ dl[i][j] = INF; ds[i][j] = INF; } } for(int i = 1; i <= n; i++){ dl[i][i] = 0; ds[i][i] = 0;} for(int i = 0; i < m; i++){ scanf("%d%d%d %c",&x,&y,&t,&sl); if(sl == 'L'){ dl[x][y] = t; dl[y][x] = t; } else { ds[x][y] = t; ds[y][x] = t; } } for(int k = 1; k <= n; k++){ for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ dl[i][j] = min(dl[i][j], dl[i][k] + dl[k][j]); ds[i][j] = min(ds[i][j], ds[i][k] + ds[k][j]); } } } scanf("%d%d",&r,&rz); for(int i = 1; i <= 200; i++){ for(int j = 0; j < r; j++){ dp[j][i] = INF; } } dp[0][rz] = 0; for(int k = 1; k < r; k++){ scanf("%d",&z); for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ dp[k][i] = min(dp[k][i], dp[k-1][j] + dl[rz][j] + ds[j][i] + dl[i][z]); if(i == j) dp[k][i] = min(dp[k][i], dp[k-1][j] + dl[rz][z]); } } rz = z; } int ans = INF; for(int i = 1; i <= n; i++) ans = min(ans, dp[r-1][i]); printf("%d\n",ans); } }