Aizu Online Judge 2200 Mr. Rito Post Office

へーあんたも離島っていうんだー（バカかお前）
陸路のみと海路のみのそれぞれのグラフにワーシャルフロイドかけてから、memo[i][j]:=島jに船を置いた状態でi番目の島を訪れたときの最短距離 でdp（拡張ダイクストラ法も時間があればまた）

#include<cstdio>
#include<algorithm>
using namespace std;
static const int MAX_N = 200;
static const int MAX_R = 1000;
static const int INF = 1 << 20;
 
int N, M;
int x, y, t; char sl;
int R;
int z[MAX_R];
 
int dist1[MAX_N][MAX_N], dist2[MAX_N][MAX_N];
int memo[MAX_R][MAX_N];
 
int main(){
    for(;;){
        scanf("%d %d", &N, &M);
        if(N == 0 && M == 0) break;
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                if(i == j){
                    dist1[i][j] = 0;
                    dist2[i][j] = 0;
                }else{
                    dist1[i][j] = INF;
                    dist2[i][j] = INF;
                }
            }
        }
        for(int i = 0; i < M; i++){
            scanf("%d %d %d %c", &x, &y, &t, &sl);
            x--; y--;
            if(sl == 'L'){
                dist1[x][y] = min(dist1[x][y], t);
                dist1[y][x] = min(dist1[y][x], t);
            }else if(sl == 'S'){
                dist2[x][y] = min(dist2[x][y], t);
                dist2[y][x] = min(dist2[y][x], t);
            }
        }
        for(int k = 0; k < N; k++){
            for(int i = 0; i < N; i++){
                for(int j = 0; j < N; j++){
                    if(dist1[i][j] > dist1[i][k] + dist1[k][j]) dist1[i][j] = dist1[i][k] + dist1[k][j];
                    if(dist2[i][j] > dist2[i][k] + dist2[k][j]) dist2[i][j] = dist2[i][k] + dist2[k][j];
                }
            }
        }
        scanf("%d", &R);
        for(int i = 0; i < R; i++){
            scanf("%d", &z[i]);
            z[i]--;
        }
        fill(memo[0], memo[R], INF);
        for(int i = 0; i < R; i++){
            for(int j = 0; j < N; j++){
                if(i == 0){
                    if(j == z[i]) memo[i][j] = 0;
                }else{
                    memo[i][j] = min(memo[i][j], min(memo[i - 1][j] + dist1[z[i - 1]][z[i]], INF));
                    for(int k = 0; k < N; k++){
                        memo[i][k] = min(memo[i][k], min(memo[i - 1][j] + dist1[z[i - 1]][j] + dist2[j][k] + dist1[k][z[i]], INF));
                    }
                }
            }
        }
        int res = INF;
        for(int i = 0; i < N; i++) res = min(res, memo[R - 1][i]);
        printf("%d\n", res);
    }
    return 0;
}