首页 > ACM题库 > HDU-杭电 > HDU 2962-Trucking-Dijkstra-[解题报告]HOJ
2014
02-24

HDU 2962-Trucking-Dijkstra-[解题报告]HOJ

Trucking

问题描述 :

A certain local trucking company would like to transport some goods on a cargo truck from one place to another. It is desirable to transport as much goods as possible each trip. Unfortunately, one cannot always use the roads in the shortest route: some roads may have obstacles (e.g. bridge overpass, tunnels) which limit heights of the goods transported. Therefore, the company would like to transport as much as possible each trip, and then choose the shortest route that can be used to transport that amount.

For the given cargo truck, maximizing the height of the goods transported is equivalent to maximizing the amount of goods transported. For safety reasons, there is a certain height limit for the cargo truck which cannot be exceeded.

输入:

The input consists of a number of cases. Each case starts with two integers, separated by a space, on a line. These two integers are the number of cities (C) and the number of roads (R). There are at most 1000 cities, numbered from 1. This is followed by R lines each containing the city numbers of the cities connected by that road, the maximum height allowed on that road, and the length of that road. The maximum height for each road is a positive integer, except that a height of -1 indicates that there is no height limit on that road. The length of each road is a positive integer at most 1000. Every road can be travelled in both directions, and there is at most one road connecting each distinct pair of cities. Finally, the last line of each case consists of the start and end city numbers, as well as the height limit (a positive integer) of the cargo truck. The input terminates when C = R = 0.

输出:

The input consists of a number of cases. Each case starts with two integers, separated by a space, on a line. These two integers are the number of cities (C) and the number of roads (R). There are at most 1000 cities, numbered from 1. This is followed by R lines each containing the city numbers of the cities connected by that road, the maximum height allowed on that road, and the length of that road. The maximum height for each road is a positive integer, except that a height of -1 indicates that there is no height limit on that road. The length of each road is a positive integer at most 1000. Every road can be travelled in both directions, and there is at most one road connecting each distinct pair of cities. Finally, the last line of each case consists of the start and end city numbers, as well as the height limit (a positive integer) of the cargo truck. The input terminates when C = R = 0.

样例输入:

5 6
1 2 7 5
1 3 4 2
2 4 -1 10
2 5 2 4
3 4 10 1
4 5 8 5
1 5 10
5 6
1 2 7 5
1 3 4 2
2 4 -1 10
2 5 2 4
3 4 10 1
4 5 8 5
1 5 4
3 1
1 2 -1 100
1 3 10
0 0

样例输出:

Case 1:
maximum height = 7
length of shortest route = 20

Case 2:
maximum height = 4
length of shortest route = 8

Case 3:
cannot reach destination

 

Spfa 解法 

/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
	Copyright (c) 2011 panyanyany All rights reserved.

	URL   : http://acm.hdu.edu.cn/showproblem.php?pid=2962
	Name  : 2962 Trucking

	Date  : Thursday, January 19, 2012
	Time Stage : one hour

	Result: 
5276304	2012-01-19 18:31:14	Accepted	2962
250MS	596K	2705 B
C++	pyy


Test Data :

Review :
根据华神指点,特用 spfa 做一次,发现邻接表要比矩阵快很多啊
//----------------------------------------------------------------------------*/

#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>

using namespace std ;

#define INF		0x3f3f3f3f
#define MAXN	1002

#define min(x, y)	((x) < (y) ? (x) : (y))
#define max(x, y)	((x) > (y) ? (x) : (y))
#define MEM(a, v)	memset (a, v, sizeof (a))

struct EDGE {
	int to ;
	int hei, dis ;
};

bool	used[MAXN] ;

int		c, r ;
int		dist[MAXN] ;

vector<EDGE>	map[MAXN] ;

int spfa (const int beg, const int end, const int lim)
{
	queue<int>	q ;
	EDGE		e ;

	int i, t ;

	MEM (dist, INF) ;
	MEM (used, 0) ;

	q.push (beg) ;
	used[beg] = 1 ;
	dist[beg] = 0 ;

	while (!q.empty ())
	{
		t = q.front () ;
		q.pop () ;

		for (i = 0 ; i < map[t].size() ; ++i)
		{
			e = map[t][i] ;
			if (e.hei >= lim && dist[t] + e.dis < dist[e.to])
			{
				// !used[e.to] 不能写到上面的判断里去。
/*
5 6
1 2 7 5
1 3 4 2
2 4 -1 10
2 5 2 4
3 4 10 1
4 5 8 5
1 5 4

在这个例子中,4 先被 3 入队,used[4] = 1,
当 3 的所有边遍历完后,遍历 2 的所有边,此时发现 4 已经入队,则 dist[4] 就无法
更新,而且 2 不会再次入队,所以 1-->4 的最短路只能经过 3,而不能经过 2。
*/

				dist[e.to] = dist[t] + e.dis ;
				if (!used[e.to])
				{
					used[e.to] = 1 ;
					q.push (e.to) ;
				}
			}
		}
		used[t] = 0 ;
	}
	return dist[end] ;
}

void init ()
{
	int i ;
	for (i = 1 ; i <= c ; ++i)
		map[i].clear () ;
}

int main ()
{
	int i ;
	int x, y, h, d ;
	int res, low, high, mid, ans ;
	int tcase ;

	tcase = 0 ;
	while (scanf ("%d%d", &c, &r), c | r)
	{
		EDGE	e ;

		init () ;

		for (i = 1 ; i <= r ; ++i)
		{
			scanf ("%d%d%d%d", &x, &y, &h, &d) ;
			h = (h == -1 ? INF : h) ;
			e.to  = y ;
			e.hei = h ;
			e.dis = d ;

			map[x].push_back(e) ;
			e.to  = x ;
			map[y].push_back(e) ;
		}
		scanf ("%d%d%d", &x, &y, &high) ;

		// 二分查找,暴力枚举所有高度
		low = 1 ;
		res = INF ;
		while (low <= high)
		{
			mid = (low + high) / 2 ;
			res = spfa (x, y, mid) ;
			if (INF == res)
				high = mid - 1 ;
			else
			{
				low = mid + 1 ;
				ans = res ;
				h   = mid ;
			}
		}
		if (tcase)
			putchar ('\n') ;
		printf ("Case %d:\n", ++tcase) ;
		if (ans != INF)
		{
			printf ("maximum height = %d\nlength of shortest route = %d\n",
				h, ans) ;
		}
		else
			printf ("cannot reach destination\n") ;
	}
	return 0 ;
}

 

Dijkstra 解法

/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
	Copyright (c) 2011 panyanyany All rights reserved.

	URL   : http://acm.hdu.edu.cn/showproblem.php?pid=2962
	Name  : 2962 Trucking

	Date  : Thursday, January 19, 2012
	Time Stage : 7 hours

	Result: 
5275934	2012-01-19 17:01:40	Accepted	2962
1843MS	8076K	2663 B
C++	pyy

Test Data :

Review :
好吧,有点太浪费时间了……
//----------------------------------------------------------------------------*/

#include <stdio.h>
#include <string.h>

#define INF		0x3f3f3f3f
#define MAXN	1002

#define min(x, y)	((x) < (y) ? (x) : (y))
#define max(x, y)	((x) > (y) ? (x) : (y))
#define MEM(a, v)	memset (a, v, sizeof (a))

bool	used[MAXN] ;

int		c, r ;
int		map[MAXN][MAXN], heig[MAXN][MAXN], dist[MAXN], hi[MAXN] ;

int dijkstra (const int beg, const int end, const int lim)
{
	int i, j ;
	int iMinPath, MinPath ;

	MEM (used, 0) ;
	MEM (hi, 0) ;
	MEM (dist, INF) ;

	for (i = 1 ; i <= c ; ++i)
	{
		// 根据华神指点,加了这里。
		// 这里不加,屡次WA
		// 虽然后面的更新操作也限制了高度,但万一起点到终点本来就有边,
		// 高度却不合适呢?
		if (heig[beg][i] >= lim)	
		{
			dist[i] = map[beg][i] ;
			hi[i] = heig[beg][i] ;
		}
	}

	// 第一次 WA 后增加下两句
	dist[beg] = 0 ;
	hi[beg] = INF ;

	for (i = 1 ; i <= c ; ++i)
	{
		iMinPath = 0 ;
		MinPath = INF ;

		for (j = 1 ; j <= c ; ++j)
		{
			if (!used[j] && 
				hi[j] >= lim &&
				dist[j] < MinPath)
			{
				iMinPath = j ;
				MinPath = dist[j] ;
			}
		}

		used[iMinPath] = 1 ;

		for (j = 1 ; j <= c ; ++j)
		{
			if (!used[j] && 
				heig[iMinPath][j] >= lim &&
				dist[iMinPath] + map[iMinPath][j] < dist[j])
			{
				dist[j] = dist[iMinPath] + map[iMinPath][j] ;
				hi[j] = min(hi[iMinPath], heig[iMinPath][j]) ;
			}
		}
	}

	return dist[end] ;
}

int main ()
{
	int i, j ;
	int x, y, h, d ;
	int res, low, high, mid, tmp1, tmp2 ;
	int tcase ;

	tcase = 0 ;
	while (scanf ("%d%d", &c, &r), c | r)
	{
		MEM(map, INF) ;
		MEM(heig, 0) ;

		for (i = 1 ; i <= r ; ++i)
		{
			scanf ("%d%d%d%d", &x, &y, &h, &d) ;
			map[x][y] = map[y][x] = d ;
			heig[x][y] = heig[y][x] = (h == -1 ? INF : h) ;
		}
		scanf ("%d%d%d", &x, &y, &h) ;
		low = 1 ;	// 第四次 WA,改为 1
		high = h ;
		res = INF ;
		while (low <= high)
		{
			mid = (low + high) / 2 ;
			tmp1 = dijkstra (x, y, mid) ;
			if (INF == tmp1)
				high = mid - 1 ;
			else
			{
				low = mid + 1 ;
				res = tmp1 ;
				tmp2 = mid ;
			}
		}
		if (tcase)
			putchar ('\n') ;
		printf ("Case %d:\n", ++tcase) ;
		if (res != INF)
		{
			printf ("maximum height = %d\nlength of shortest route = %d\n",
				tmp2, res) ;
		}
		else
			printf ("cannot reach destination\n") ;
	}
	return 0 ;
}

 

解题参考:http://blog.csdn.net/panyanyany/article/details/7211266


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥

  3. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样:push时,比较要push的elem和辅助栈的栈顶,elem<=min.top(),则min.push(elem).否则只要push(elem)就好。在pop的时候,比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();},否则{stack.pop();}.