Description

你是在离岛邮局工作的程序员。你所居住的地区，由多个岛屿组成。每个岛屿都有一个或多个港口城市。除了它们之外，还可能有其他城镇或村庄。要想从一个岛屿驶往另一个岛屿，就必须使用船只。要在一个岛屿中转，可以使用陆路，但是，有时使用海路更快。

以近年来进行的邮局私有化为契机，为了削减经费，在全国范围内进行了邮递员的人员整理。离岛的邮局也不例外，结果邮递员只有利藤先生一个人。由于该邮局负责集配的地域非常广，一个人集配是一项艰巨的工作。所以，利藤先生一直在向你求助，如何才能有效地进行集配呢？

你的工作就是在给出利藤先生应该追溯的城镇和村庄的集配顺序时，写出寻求最短巡回路线的程序。

利藤先生决不能在指定的顺序以外办理集配业务。但是，在从一个城镇或村庄移动到另一个城镇或村庄时，获准经由其他城镇或村庄进行移动。此外，利藤先生还拥有一艘船只，用来绕岛而行。？

例如，在被赋予了城镇A、城镇B、村C的集配顺序的情况下，从A到B时经由哪个城镇或村都没有关系。此时，虽然经由村C也可以，但是为了遵守集配顺序，在去城镇B进行一次集配之后，必须再次访问村C进行集配。另外，从城镇A使用海路前往城镇B，从城镇B使用陆路前往村C时，将船放在城镇B中。因此，下次想使用海路时有必要返回城镇B。

也有在一个城镇或村庄中必须进行多次集配的情况。例如，可能会给出城镇A、村庄B、城镇C、村庄B这样的集配顺序。此时，从城镇A不追溯到村庄B而前往城镇C的情况下，不能在城镇C突然进行集配，因为最初的村B的集配没有结束。即使在城镇C完成集配后访问村B进行集配，也不会结束第一次村B的集配。

利藤先生首先一定会在某港口城市随船。由于利藤先生是资深人士，所以可以忽略流动时间以外的集配工作所花费的时间。此外，只有在最后一个城镇或村庄完成集配业务所需的时间才是问题，不用考虑把船送回原来位置返回邮局所需的时间。

输入

输入由多个数据集构成。各数据集的形式如下所示。
N M
x1 y1 t1 sl1
x2 y2 t2 sl2
xM yM tM slM
R
z1 z2 … zR
数据集中的输入项目，均为非负整数。行中输入项目的分隔符为空白一个。

第一行，规定陆路及海路网的大小。

N(2≤N≤200)是城镇或村庄的数量。在每个城镇或村庄，从1~N分配到为止的固有号码。M(1≤M≤10000)是陆路和海路的合计条数。

从第2行开始1+M行是陆路或海路的记述。xi，yi(1≤xi, yi ≤ N)表示两端城镇或村庄的编号。ti(1≤ti≤1000)表示其陆路或海路的移动时间。sli是‘L’或‘S’中的任意一个，L表示陆路，S表示海路。

有时存在两条或两条以上直接连接某两个城镇或村庄的陆路或海路。每条陆路或海路是双向的，即可以朝任何方向移动。

第M+2行的R(1≤R≤1000)表示利藤先生负责的集配单位的数量。第M+3行，集配单位的城镇和村庄编号zi(1≤zi ≤ N)以收集和分配的顺序R排着一个。

在初期状态下利藤和船都是港口城市z1存在。从初期状态到集配地点的城镇和村庄，一定可以用某种方法移动。

输入的结尾以包含以空格分隔的两个0的一行表示。

输出

对于输入的各数据集，按照给定的集配顺序求出利藤在城镇和村庄巡回所需的最短移动时间，输出到一行。

样例输入

3 3
1 2 5 L
1 2 7 S
2 3 11 S
3
1 2 3
5 5
1 2 15 L
2 3 10 L
4 5 7 L
1 3 30 S
3 4 100 S
5
1 3 5 4 1
0 0

输出样例

18
269

题解

floyd，dp

• 先预处理海路和陆路的最短路
• dp[i][j]表示到达第i个目的地时船停在j处时的最小值
• 转移：枚举上个停船点k
  if k == j 则直接走陆路z[i-1]->z[i]
  if k != j 则先从z[i-1]走陆路到k(若z[i-1] == k ，则该花费为0)，再从k走海路到j，最后从j走陆路到z[i]

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#include<sstream>
#include<set>
#include<bitset>
#include<vector>
#include<cmath>
using namespace std;
#define ios ios::sync_with_stdio(false)
const double pi=acos(-1.0);
int dx[]={-1,0,1,0,0},dy[]={0,1,0,-1,0};
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<int,double> PID;
const int INF=0x3f3f3f3f;
const LL LNF=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;

const int N=210,M=1010;
int dl[N][N];//陆路
int ds[N][N];//海陆
int a[M];//访问顺序
LL f[M][N];//dp[i][j]: 已经走了前i个地方，当前船停在j点的最短移动时间
int n,m,r;

void init()
{
    memset(dl,0x3f,sizeof dl);
    memset(ds,0x3f,sizeof ds);
    for(int i=1;i<=n;i++)
        dl[i][i]=ds[i][i]=0;
}

void floyd()
{
    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]);
}

int main()
{
    while(cin>>n>>m)
    {
        if(!n && !m) break;

        init();

        while(m--)
        {
            int a,b,c;
            char t;
            cin>>a>>b>>c>>t;
            if(t == 'L')
                dl[a][b]=dl[b][a]=min(dl[a][b],c);
            else
                ds[a][b]=ds[b][a]=min(ds[a][b],c);
        }

        cin>>r;

        for(int i=1;i<=r;i++) cin>>a[i];

        floyd();

        memset(f,0x3f,sizeof f);
        f[1][a[1]]=0;

        for(int i=2;i<=r;i++)
            for(int j=1;j<=n;j++)
                for(int k=1;k<=n;k++)
                    if(j != k) f[i][j]=min(f[i][j],f[i-1][k]+dl[a[i-1]][k]+ds[k][j]+dl[j][a[i]]);
                    else f[i][j]=min(f[i][j],f[i-1][j]+dl[a[i-1]][a[i]]);

        LL ans=LNF;
        for(int i=1;i<=n;i++) ans=min(ans,f[r][i]);
        cout<<ans<<endl;
    }
    // system("pause");
}