AOJ 2200 Mr. Rito Post Office 题解 《挑战程序设计竞赛》

AOJ 2200 Mr. Rito Post Office

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

2.5 它们其实都是“图”

最短路

先单独考虑只走水路或旱路的情况，用warshall_floyd求出任意两点间的最短路。

然后定义 dp[i][k] := 已经去了第i个镇子后，船停在第k个镇子里的状态下的最短路。

然后ijk三重循环更新dp，其中递推公式思路：

在推导ik的时候，定义一个中间状态j表示先从i-1走旱路到j，然后从j走水路去k，最后从k走旱路去i，于是就把船扔在了k。如果j==k的时候就不需要绕圈子了。

#include <iostream>
#include <algorithm>
using namespace std;

#define INF 1e8
#define MAX_V 256
#define MAX_R 1024
int dl[MAX_V][MAX_V];	//	d[u][v]表示边e=(u,v)的权值，不存在的时候等于无穷大或者d[i][i] = 0
int ds[MAX_V][MAX_V];
int z[MAX_R];
int dp[MAX_R][MAX_V];	// dp[i][j] := 已经去了第i个镇子后，船停在第j个镇子里
int N;					//	顶点数

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{

	int M;
	while (cin >> N >> M , N || M)
	{
// 		memset(dl, 0x3f, sizeof(dl));
// 		memset(ds, 0x3f, sizeof(ds));
		for (int i = 0; i < N; ++i)
		{
			for (int j = 0; j < N; ++j)
			{
				if (i == j)
				{
					dl[i][j] = ds[i][j] = 0;
				}
				else
				{
					dl[i][j] = ds[i][j] = INF;
				}
			}
		}

		for (int i = 0; i < M; ++i)
		{
			int x, y, t;
			char s;
			cin >> x >> y >> t >> s;
			--x; --y;
			if (s == 'L')
			{
				dl[x][y] = min(dl[x][y], t);
				dl[y][x] = dl[x][y];
			}
			else
			{
				ds[x][y] = min(ds[x][y], t);
				ds[y][x] = ds[x][y];
			}
		}
		
		int R;
		cin >> R;
		for (int i = 0; i < R; ++i)
		{
			cin >> z[i];
			--z[i];
		}

		// warshall_floyd
		for (int k = 0; k < N; ++k)
		{
			for (int i = 0; i < N; ++i)
			{
				for (int j = 0; 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]);
				}
			}
		}
		// end of warshall_floyd

		// dp
		// 尼玛3个0x3f3f3f3f加起来溢出了
		//memset(dp, 0x3f, sizeof(dp));
		for (int i = 0; i < R; ++i)
		{
			for (int j = 0; j < N; ++j)
			{
				dp[i][j] = INF;
			}
		}
		for (int i = 0; i < N; ++i)
		{
			// 去了首个镇子后，船放在第i个镇子里
						// 坐船去	 // 坐11路车回来
			dp[0][i] = ds[z[0]][i] + dl[i][z[0]];
		}
		for (int i = 1; i < R; ++i)
		{
			for (int j = 0; j < N; ++j)
			{
				for (int k = 0; k < N; ++k)
				{
					if (j != k)
					{
						//                          i-1站     + 从i-1站走旱路去j+ 从j走水路去k+从k走旱路去i
						dp[i][k] = min(dp[i][k], dp[i - 1][j] + dl[z[i - 1]][j] + ds[j][k] + dl[k][z[i]]);
					}
					else
					{
						// j == k                   i-1站     + 从i-1站走旱路去i
						dp[i][j] = min(dp[i][j], dp[i - 1][j] + dl[z[i - 1]][z[i]]);
					}
				}
			}
		}

		cout << *min_element(dp[R - 1], dp[R - 1] + N) << endl;
	}

	return 0;
}
///////////////////////////End Sub//////////////////////////////////

啊，真是蛋疼的一题。发生了小插曲，先是3个0x3f3f3f3f加起来溢出了，后是数组开小了导致WA。唉，这玩意儿很吃时间，明明算法都搞明白了，就是不AC的心情，你懂得。

 知识共享署名-非商业性使用-相同方式共享：码农场 » AOJ 2200 Mr. Rito Post Office 题解 《挑战程序设计竞赛》