【最短路+dijkstra+spfa】杭电 hdu 2962 Trucking

 

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 ;
}

 

Dijks解法

 

/* 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 ;
}