hdu2962 二分 + spfa

题意:
      给你一个无向图,每条路径上都有自己的长度和最大承受高度,给你起点终点还有车的最大承装高度,问你高度最大的前提下路径最短是多少,求高度和路径.


思路:

     这种类型题目太多了,就是给你一些限制,然后让你在这个限制的前提下找到另一个最优,涉及到线性单调的一般都可以直接二分枚举a掉,这个也不例外,二分高度,重新建图,或者在跑最短路的时候限制,都可以,具体看代码就懂了..

#include<stdio.h> #include<string.h> #include<queue>#define N_node 1000 + 100 #define N_edge 1000000 + 500 #define INF 1800000000 using namespace std;typedef struct {int to ,cost ,next; }STAR;typedef struct {int a ,b ,c ,d; }EDGE;EDGE edge[N_edge]; STAR E[N_edge]; int list[N_node] ,tot; int s_x[N_node];void add(int a ,int b ,int c) {E[++tot].to = b;E[tot].cost = c;E[tot].next = list[a];list[a] = tot; }void spfa(int s ,int n) {for(int i = 0 ;i <= n ;i ++)s_x[i] = INF; int mark[N_node] = {0};s_x[s] = 0;mark[s] = 1;queue<int>q;q.push(s);while(!q.empty()){int xin ,tou;tou = q.front();q.pop();mark[tou] = 0;for(int k = list[tou] ;k ;k = E[k].next){xin = E[k].to;if(s_x[xin] > s_x[tou] + E[k].cost){s_x[xin] = s_x[tou] + E[k].cost;if(!mark[xin]){mark[xin] = 1;q.push(xin);}}}}return ; }bool ok(int mid ,int s ,int t ,int n ,int m) {memset(list ,0 ,sizeof(list));tot = 1;for(int i = 1 ;i <= m ;i ++)if(edge[i].c == -1 || edge[i].c >= mid){add(edge[i].a ,edge[i].b ,edge[i].d);add(edge[i].b ,edge[i].a ,edge[i].d);}spfa(s ,n);return s_x[t] != INF; }int main () {int n ,m ,i ,j;int s ,t ,w ,cas = 1;while(~scanf("%d %d" ,&n ,&m) && n + m){if(cas != 1) puts("");for(i = 1 ;i <= m ;i ++)scanf("%d %d %d %d" ,&edge[i].a ,&edge[i].b ,&edge[i].c ,&edge[i].d);scanf("%d %d %d" ,&s ,&t ,&w);int up ,low ,mid;low = 0,up = w;int answ = -1 ,ansl;while(low <= up){mid = (low + up) >> 1;if(ok(mid ,s ,t ,n ,m)){low = mid + 1;answ = mid;ansl = s_x[t];}elseup = mid - 1;}printf("Case %d:\n" ,cas ++);if(answ == -1)printf("cannot reach destination\n");else{printf("maximum height = %d\n" ,answ);printf("length of shortest route = %d\n" ,ansl);}}return 0; }

总结

以上是生活随笔为你收集整理的hdu2962 二分 + spfa的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。