Aizu：2200

Aizu：2200"/>

Aizu：2200

快递

Time limit 8000 ms
Memory limit 131072 kB

Problem Description

你是某个岛国（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的时候表示终止。

Sample Input

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

Output for the Sample Input

18
269

解题新的：

1. 这个题主要考察的是一个动态规划，其实Floyd就是一个动态规划，然后数据量有点大，时间给的很大，整个解题的过程也非常的暴力。
2. 首先要明白水路和陆路是不能够只建立一张图的，水路需要建立一张图，陆路需要建立一张图，然后分别跑Floyd，得到同一种路中每两点之间的最短距离，然后动态规划，得到水路陆路混合跑的最短距离。

//cost[i][j]表示从i点走到j点需要花费的最少时间#include <stdio.h>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;const int maxn = 1010;
const ll INF = 0x1f1f1f1f1f1f1f1f;
ll odr[maxn],cost[maxn][maxn],sea_path[maxn][maxn],land_path[maxn][maxn],n,m,w;void init() {memset(cost,INF, sizeof(cost));memset(sea_path,INF, sizeof(sea_path));memset(land_path,INF, sizeof(land_path));char s[5];for(int i=0;i<m;i++) {ll a,b,c;scanf("%lld%lld%lld%s",&a,&b,&c,s);if(s[0] == 'S')//建立两个图sea_path[a][b] = sea_path[b][a] = min(sea_path[a][b],c);elseland_path[a][b] = land_path[b][a] = min(land_path[a][b],c);}scanf("%lld",&w);for(int i=1;i<=w;i++)scanf("%lld",&odr[i]);//将要走的地点给存起来}void Floyd() {//用Floyd来预处理任意两点之间的最短距离for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++) {sea_path[i][j] = min(sea_path[i][j],sea_path[i][k]+sea_path[k][j]);land_path[i][j] = min(land_path[i][j],land_path[i][k]+land_path[k][j]);}
}void get_ans() {for(int i=1;i<=n;i++)sea_path[i][i] = land_path[i][i] = 0;//自身到自身时间花费为0cost[1][odr[1]] = 0;for(int i=1;i<=w;i++) {for(int j=1;j<=n;j++) {cost[i][j] = min(cost[i][j],cost[i-1][j]+land_path[odr[i-1]][odr[i]]);//假如走的是陆路for(int k=1;k<=n;k++) {//枚举船停的位置cost[i][k] = min(cost[i][k],cost[i-1][j]+land_path[odr[i-1]][j]+sea_path[j][k]+land_path[k][odr[i]]);//从i-1点回到船在的j点，然后开船到k，再从陆路k到i点}}}ll Min = 1e12;for(int i=1;i<=n;i++)Min = min(cost[w][i],Min);printf("%lld\n",Min);
}int main() {while(scanf("%lld%lld",&n,&m) && n+m) {init();Floyd();get_ans();}return 0;
}

转载于:.html