2014
02-24

# 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 */
/*----------------------------------------------------------------------------//

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 :

//----------------------------------------------------------------------------*/

#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

*/

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

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