【最短路+枚举】HDU 2962 Trucking【2012-1-20更新】
KIDx 的解题报告
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2962
题意：找能够到达终点的最大高度下的最短路
这样的效率排第七，，中规中矩吧，用的是前插链接表的spfa实现，当然我还开了输入外挂，此代码中木有加外挂
http://dl.iteye.com/upload/attachment/0062/3265/77b3a497-dd01-38e9-b4cf-7284e074c12a.jpg
#include <iostream>#include <queue>using namespace std;#define inf 0x3fffffff#define M 1005struct edge{int v, w, h, next;}e;int pre, cnt, dist, n;bool inq;void init (){cnt = 0;memset (pre, -1, sizeof(pre));}void addedge (int u, int v, int w, int h) //慢慢模拟就会明白的{e.v = v;e.w = w;e.h = h;e.next = pre; //接替已有边pre = cnt++; //自己成为u派生的第一条边}void spfa (int u, int lim){int v, w, i;for (i = 1; i <= n; i++)dist = inf, inq = false;dist = 0;queue<int> q;q.push (u);inq = true;while (!q.empty()){u = q.front();q.pop();inq = false;for (i = pre; i != -1; i = e.next){if (e.h < lim) continue;w = e.w;v = e.v;if (dist + w < dist){dist = dist + w;if (!inq){q.push (v);inq = 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 != inf)l = mid, res = dist;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]