aoj2200:Mr.Rito_Post_Office.cpp

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF=1001001001001001LL;
int N,M;
int A[200][200],B[200][200];
int dp[2][200];
signed main(){
    while(cin>>N>>M,N||M){
        fill_n(*A,200*200,INF);
        fill_n(*B,200*200,INF);
        for(int i=0;i<N;i++){
            A[i][i]=0;
            B[i][i]=0;
        }
        for(int i=0;i<M;i++){
            int a,b,c;
            char d;
            cin>>a>>b>>c>>d;
            a--;b--;
            if(d=='L')A[a][b]=A[b][a]=min(A[a][b],c);
            else B[a][b]=B[b][a]=min(B[a][b],c);
        }
 
        for(int k=0;k<N;k++){
            for(int i=0;i<N;i++){
                for(int j=0;j<N;j++){
                    A[i][j]=min(A[i][j],A[i][k]+A[k][j]);
                    B[i][j]=min(B[i][j],B[i][k]+B[k][j]);
                }
            }
        }
 
        int R;cin>>R;
        int prev;cin>>prev;prev--;
        fill_n(*dp,2*200,INF);
        dp[1][prev]=0;
 
        for(int i=1;i<R;i++){
            int cur;cin>>cur;cur--;
            for(int j=0;j<N;j++){
                for(int k=0;k<N;k++){
                    if(j!=k)dp[(i+1)&1][j]=min(dp[(i+1)&1][j],dp[i&1][k]+A[prev][k]+B[k][j]+A[j][cur]);
                    else dp[(i+1)&1][j]=min(dp[(i+1)&1][j],dp[i&1][j]+A[prev][cur]);
                }
            }
            for(int j=0;j<N;j++)dp[i&1][j]=INF;
            prev=cur;
        }
 
        int mi=INF;
        for(int i=0;i<N;i++)mi=min(mi,dp[R&1][i]);
 
        cout<<mi<<endl;
    }
    return 0;
}