HDU 2962 Trucking 最短路+二分

本文主要是介绍HDU 2962 Trucking 最短路+二分，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目来源 HDU 2962 Trucking

题意：给你一张无向图n个点m条边 给出起点s终点e和最大承受的高度 其中每条路都有限制的高度以及该条路的长度 求从s到e最大可以通过的高度和在最大高度的前提下的最短路

思路：二分高度再求最短路 无解特判一下

#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int maxn = 1010;
struct edge
{int u, v, h, w;
};
struct HeapNode
{int u, d;bool operator < (const HeapNode& rhs)const{return d > rhs.d;}
};
vector <edge> G[maxn];
int dis[maxn];
bool vis[maxn];
int n, m;
int s, e;
void Dijkstra(int h)
{for(int i = 0; i <= n; i++)dis[i] = 999999999;//memset(dis, 0x7f, sizeof(dis));dis[s] = 0;memset(vis, false, sizeof(vis));priority_queue <HeapNode> Q;Q.push((HeapNode){s, 0});while(!Q.empty()){HeapNode x = Q.top();Q.pop();int u = x.u;if(vis[u])continue;vis[u] = true;for(int i = 0; i < G[u].size(); i++){	 edge e = G[u][i];if(e.h < h)continue;int v = e.v;if(dis[v] > x.d + e.w){dis[v] = x.d + e.w;Q.push((HeapNode){v, dis[v]});	}}}
}
int main()
{int cas = 0;while(scanf("%d %d", &n, &m) && (n+m)){for(int i = 0; i <= n; i++)G[i].clear();	for(int i = 0; i < m; i++){int u, v, h, w;scanf("%d %d %d %d", &u, &v, &h, &w);if(h == -1)h = 999999999;G[u].push_back((edge){u, v, h, w});G[v].push_back((edge){v, u, h, w});			}int lim;scanf("%d %d %d", &s, &e, &lim);int l = 0, r = lim, ans = -1, len;while(l <= r){int mid = (l + r) >> 1;Dijkstra(mid);if(dis[e] != 999999999){ans = mid;len = dis[e];l = mid + 1;}else{r = mid - 1;}}if(cas++)puts("");printf("Case %d:\n", cas);if(ans == -1){puts("cannot reach destination");continue;}printf("maximum height = %d\n", ans);printf("length of shortest route = %d\n", len);}return 0;
}

 

这篇关于HDU 2962 Trucking 最短路+二分的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---