本文主要是介绍nyoj 1002 Trucking，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
同样一道改编题。
只要把题意理解了好。
简单的二分加最短路。
只要二分高度，
然后求最短路，输出满足题意的即可。
代码如下：
（最短路用spfa 时间效率高）
#include <iostream>
#include <cstdio>
#include <cstring>
#include <ctime>
#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()
{//freopen("in2.txt","r",stdin);//freopen("in1.txt","w",stdout);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");}//printf("TIME used = %.4lf\n",(double)clock()/CLOCKS_PER_SEC);return 0;
} 这篇关于nyoj 1002 Trucking的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
