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

【最短路+枚举】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 1005struct 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;}