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

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