旅行 - nazgul's Blog

The QianJin Teaching Building

旅行

nazgul posted @ 2010年10月18日 23:48 in HNU , 1044 阅读

小王最近刚买了新车，非常兴奋，于是决定开车出去旅游。但是从他家到旅游目的地没有直接连接的道路，他中间必须经过其他的城市才能到达目的地。

一开始时，他的汽车每单位时间走单位路程，但是当经过一个城市后，他需要增加一个单位时间才能走单位路程，请编程计算他如何开车才能最快到达目的地。

输入：第一行是测试用例个数。对每一个测试用例，第一行是两个数n and m (0 < n ≤ 200, 0 < m < n×(n-1)/2 )，n是城市的编号，编号1是他的出发点，n是目的地，m是城市之间存在的路的条数，道路可双向行驶。

接来的m行，每行包含3个数x, y, z，表示从城市x到城市y有一条道路，距离是z，（假设从家到目的地总至少有一条通路）。

输出：从家到目的地最少的时间。

样例输入：

5 6

1 2 1

1 4 5

2 3 2

3 5 1

4 5 1

2 4 2

样例输出：

本题不能用一般的最短路来求，因为并不一定是每次都走最短的边就能得出最小值。

我们可以认为每条边的权值为k*x，k为边的初始权值，x为该走法经过的点的个数，最开始x为1，如果我们按x逐步增大来递推，那么可以知道，如果一个节点第x(x>1)

次经过时，只有当走这条路到达这个点的花费小于之前到达该点的最小值，这样走才可能使这次更新有意义。

因此我们可以定义一个3重循环，第一重为步数x，第2重为该步数有被更新的点i，如果i有在第x步被更新则进入第3重循环让他们去更新他们能到达的其他点，当所有点无法被更新时结束。最坏的情况下时间复杂度为n3。


#include <stdio.h>
#include <string.h>
#define MAX 0x7f7f7f7f

int d[501][501],dis[501][501],mx[501],pre[501];
int main()
{
	int tt, bb;
	int n, m, i, j, x, y, z, flag;

	scanf( "%d", &tt );
	for ( bb=0; bb<tt; bb++)
	{
		scanf( "%d%d", &n, &m );
		memset( d, 0, sizeof( d ) );
		for ( i=1; i<=m; i++ )
		{
			scanf( "%d%d%d", &x, &y, &z );
			d[x][y] = d[y][x] = z;
		}
		memset( mx, 127, sizeof( mx ) );
		memset( dis, 127, sizeof( dis ) );
		dis[0][1] = 0; mx[1] = 0;
		for ( x=0; ; x++ )
		{
			for ( flag=0, i=1; i<=n; i++ )
			{
				if ( dis[x][i] != MAX )
				{
					flag = 1;
					for ( j=1; j<=n; j++ )
					{
						if ( d[i][j] != 0 && mx[j] > dis[x][i] + d[i][j]*( x+1 ) )
						{
							mx[j] = dis[x][i] + d[i][j]*(x+1);
							dis[x+1][j] = mx[j];
						}
					}
				}
			}
			if ( flag == 0 ) break;
		}
		printf("%d\n",mx[n]);
    }
    return 0;
 }