hdu 2962 Trucking (最短路之SPFA算法 + 二分)

发布时间:2016-12-11 20:18:56 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"hdu 2962 Trucking (最短路之SPFA算法 + 二分)",主要涉及到hdu 2962 Trucking (最短路之SPFA算法 + 二分)方面的内容,对于hdu 2962 Trucking (最短路之SPFA算法 + 二分)感兴趣的同学可以参考一下。

Trucking                                                                      Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Problem Description 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.   Input 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.   Output For each case, print the case number followed by the maximum height of the cargo truck allowed and the length of the shortest route. Use the format as shown in the sample output. If it is not possible to reach the end city from the start city, print "cannot reach destination" after the case number. Print a blank line between the output of the cases.   Sample Input 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   Sample Output 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   题意:一个运输公司想把一些货物从起点运到终点,每次运送的货物越多越好。但是一些道路有高度限制,所以不能只考虑路线最短。给出城市和道路的数量、每条道路的端点及高度限制和长度、起点、终点、汽车最大的载物高度,求在载物最多的情况下的最大高度和最短路径长度,即能够到达终点的最大高度下的最短路。如果从起点不能到达终点,输出"cannot reach destination"。 看到这个题后,不知道如何去平衡高度和最短路这两个条件,后来看了别人的题解,才知道二分求出最大高度,然后在最大高度下求出最短路就行了。看来我还是太菜了。 #include<stdio.h> #include<string.h> #include<queue> using namespace std; #define INF 0x3fffffff const int N = 1010; int n, C, R; int first[N], dis[N]; struct edge { int u, v, w, h, next; }e[N*N]; void AddEdge(int u, int v, int w, int h) { e[n].u = u; e[n].v = v; e[n].w = w; e[n].h = h; e[n].next = first[u]; first[u] = n++; } void SPFA(int start, int limit) { queue<int> q; bool inq[N]; for(int i = 1; i <= C; i++) dis[i] = INF, inq[i] = false; dis[start] = 0; q.push(start); inq[start] = true; while(!q.empty()) { int x = q.front(); q.pop(); inq[x] = false; for(int i = first[x]; i != -1; i = e[i].next) { if(e[i].h < limit) continue; if(dis[x] + e[i].w < dis[e[i].v]) { dis[e[i].v] = dis[x] + e[i].w; if(!inq[e[i].v]) { q.push(e[i].v); inq[e[i].v] = true; } } } } } int main() { int u, v, h, l, i, j, cas = 1; while(~scanf("%d%d",&C,&R) && (C + R)) { if(cas > 1) printf("\n"); n = 0; memset(first, -1, sizeof(first)); for(i = 0; i < R; i++) { scanf("%d%d%d%d",&u, &v, &h, &l); if(h == -1) h = INF; AddEdge(u, v, l, h); AddEdge(v, u, l, h); //头插法添加双向边 } int st, ed, limhet; scanf("%d%d%d",&st, &ed, &limhet); int l = 0, r = limhet, ans = INF, mid; while(l <= r) //二分枚举高度,使高度尽量大 { mid = (l + r) / 2; SPFA(st, mid); if(dis[ed] != INF) { l = mid + 1; ans = dis[ed]; } else r = mid - 1; } printf("Case %d:\n",cas++); if(ans != INF) { printf("maximum height = %d\n", r); printf("length of shortest route = %d\n",ans); } else printf("cannot reach destination\n"); } return 0; }

上一篇:Unix 的缺陷 - 王垠
下一篇:Confluence IM 状态宏

相关文章

相关评论