題目來源 HDU 2962
題意：給你一張無向圖n個點m條邊 給出起點s終點e和最大承受的高度 其中每條路都有限制的高度以及該條路的長度 求從s到e最大可以通過的高度和在最大高度的前提下的最短路
思路：二分高度再求最短路 無解特判一下
#include#include #include #include 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 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 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; }
