Aizu 2200 Mr. Rito Post Office【特复杂的floyd+dp】

Rito Post Office【特复杂的floyd+dp】"/>

Aizu 2200 Mr. Rito Post Office【特复杂的floyd+dp】

原题网址：

.jsp?id=2200

快递

你是某个岛国（ACM-ICPC Japan）上的一个苦逼程序员，你有一个当邮递员的好基友利腾桑遇到麻烦了：全岛有一些镇子通过水路和旱路相连，走水路必须要用船，在X处下船了船就停在X处。而且岛上只有一条船，下次想走水路还是得回到X处才行；两个镇子之间可能有两条以上的水路或旱路；邮递员必须按照清单上的镇子顺序送快递（镇子可能重复，并且对于重复的镇子不允许一次性处理，比如ABCB的话B一定要按顺序走两次才行）。

测试数据有多组：

N M

x1 y1 t1 sl1

x2 y2 t2 sl2

…

xM yM tM slM

R

z1 z2 … zR

N (2 ≤ N ≤ 200) 是镇子的数量，M (1 ≤ M ≤ 10000) 是旱路和水路合计的数量。从第2行到第M + 1行是路径的描述，路径连接xi  yi两地，路径花费 ti (1 ≤ ti ≤ 1000)时间，sli 为L时表示是旱路，S时表示是水路。可能有两条及以上路径连接两个镇子，并且路径都是双向的。

M + 2行的R是利腾需要去的镇子的数量，M + 3是利腾需要去的镇子的编号。

初始状态利腾和船都在第一个镇子，且肯定有方法达到需要去的镇子。

测试数据为0 0的时候表示终止。

翻译及题解来源点此处

做这道题的时候，内心几乎是崩溃的......

首先是语言不通，看不懂题意，然后是发现好复杂，貌似只能暴力枚举，然而各种条件过多，实在难以找到枚举的方式...........

膜拜会做的大神，这道题与其说是最短路，不如说完全是动态规划了.........（其实最短路就是dp...）

/*

*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll inf=0x1f1f1f1f1f1f1f1f;//构造了一个三倍之后不会溢出的值..... 
const ll maxn=205;
ll land[maxn][maxn],sea[maxn][maxn],num[maxn*5],cost[maxn*5][maxn];
void init(int n)
{memset(land,inf,sizeof(land));memset(sea,inf,sizeof(sea));memset(cost,inf,sizeof(cost));for(ll i=1;i<=n;++i){sea[i][i]=land[i][i]=0;}
}
ll slove(ll n,ll m,ll w)
{for(ll k=1;k<=n;++k)//最短路{for(ll i=1;i<=n;++i){for(ll j=1;j<=n;++j){sea[i][j]=min(sea[i][j],sea[i][k]+sea[k][j]);land[i][j]=min(land[i][j],land[i][k]+land[k][j]);}}}cost[1][num[1]]=0;for(ll i=1;i<=w;++i)//这算是暴力枚举吧....{for(ll j=1;j<=n;++j){cost[i][j]=min(cost[i][j],cost[i-1][j]+land[num[i-1]][num[i]]);//走陆地for(ll k=1;k<=n;++k)//枚举走水路{cost[i][k]=min(cost[i][k],cost[i-1][j]+land[num[i-1]][j]+sea[j][k]+land[k][num[i]]);}}}ll ans=inf;for(ll i=1;i<=n;++i)//计算最小的花费{ans=min(ans,cost[w][i]);}return ans;
}
int main()
{ll n,m;while(scanf("%lld%lld",&n,&m),n|m){init(n);for(ll i=0;i<m;++i){ll a,b,c;char ch[10];scanf("%lld%lld%lld%s",&a,&b,&c,ch);if(ch[0]=='S'){sea[a][b]=sea[b][a]=min(sea[a][b],c);}else{land[a][b]=land[b][a]=min(land[a][b],c);}}ll w;scanf("%lld",&w);for(ll i=1;i<=w;++i){scanf("%lld",&num[i]);//任务对应的城市}printf("%lld\n",slove(n,m,w));}return 0;
}