【最短路+枚举】HDU 2962 Trucking【2012-1-20更新】

KIDx 的解题报告

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2962

题意：找能够到达终点的最大高度下的最短路

这样的效率排第七，，中规中矩吧，用的是前插链接表的spfa实现，当然我还开了输入外挂，此代码中木有加外挂

#include <iostream>
#include <queue>
using namespace std;
#define inf 0x3fffffff
#define M 1005

struct edge{
	int v, w, h, next;
}e[2000005];

int pre[M], cnt, dist[M], n;
bool inq[M];

void init ()
{
	cnt = 0;
	memset (pre, -1, sizeof(pre));
}

void addedge (int u, int v, int w, int h)    //慢慢模拟就会明白的
{
	e[cnt].v = v;
	e[cnt].w = w;
	e[cnt].h = h;
	e[cnt].next = pre[u];    //接替已有边
	pre[u] = cnt++;          //自己成为u派生的第一条边
}

void spfa (int u, int lim)
{
	int v, w, i;
	for (i = 1; i <= n; i++)
		dist[i] = inf, inq[i] = false;
	dist[u] = 0;
	queue<int> q;
	q.push (u);
	inq[u] = true;
	while (!q.empty())
	{
		u = q.front();
		q.pop();
		inq[u] = false;
		for (i = pre[u]; i != -1; i = e[i].next)
		{
			if (e[i].h < lim) continue;
			w = e[i].w;
			v = e[i].v;
			if (dist[u] + w < dist[v])
			{
				dist[v] = dist[u] + w;
				if (!inq[v])
				{
					q.push (v);
					inq[v] = true;
				}
			}
		}
	}
}

int main()
{
	int m, u, v, w, h, l, r, mid, cc = 1, res;
	while (scanf ("%d%d", &n, &m), (n||m))
	{
		if (cc > 1) printf ("\n");
		init();
		while (m--)
		{
			scanf ("%d%d%d%d", &u, &v, &h, &w);
			if (h == -1) h = inf;
			addedge (u, v, w, h);
			addedge (v, u, w, h);    //双向前插加边
		}
		scanf ("%d%d%d", &u, &v, &h);
		l = 0, r = h, res = inf;
		while (l < r)    //简单二分枚举高度，使高度尽量大
		{
			mid = (l+r+1) >> 1;
			spfa (u, mid);
			if (dist[v] != inf)
				l = mid, res = dist[v];
			else r = mid - 1;
		}
		printf ("Case %d:\n", cc++);
		if (res != inf)
		printf ("maximum height = %d\nlength of shortest route = %d\n", l, res);
		else puts ("cannot reach destination");
	}
    return 0;
}

评论

1 楼 panyanyany 2012-01-19  

膜拜华神 Orz .....