hdu2962Trucking 二分+最短路

分类：最短路二分

最短路-二分

;const int maxn = 1010 ;const int inf = 0x3f3f3f3f ;int vis[maxn] , dis[maxn] ;struct Edge{int v , w , h ;int next ;}edge[maxn*maxn] ;int head[maxn] , nedge ,n;void addedge(int u , int v , int h, int w){edge[nedge].v = v ;edge[nedge].h = h ;edge[nedge].w = w ;edge[nedge].next = head[u] ;head[u] = nedge++ ;}bool dijkstra(int st , int en , int h){memset(vis , 0 , sizeof(vis)) ;for(int i = 1;i <= n;i++)dis[i] = i == st ? 0 : inf ;while(1){int mi = inf ;int pos ;for(int i = 1;i <= n;i++)if(!vis[i] && dis[i] < mi)mi = dis[pos = i] ;if(mi == inf)break ;vis[pos] = 1 ;for(int i = head[pos] ; i != -1 ;i = edge[i].next){if(edge[i].h < h)continue ;int v = edge[i].v ;if(dis[v] > dis[pos] + edge[i].w)dis[v] = dis[pos] + edge[i].w ;}}if(dis[en] != inf)return true ;;}int find(int st , int en , int lim){int l = 0 ;int r = lim ;while(l <= r){int mid = (l + r) >> 1 ;if(dijkstra(st , en , mid))l = mid + 1 ;else r = mid – 1 ;}return r ;}int main(){ // freopen(“in.txt” ,”r” , stdin) ;int m , st , en , lim ;int cas = 0 ;while(scanf(“%d%d” ,&n , &m) && (n + m)){memset(head , -1 , sizeof(head)) ;nedge = 0 ;while(m–){int u , v , h , w ;scanf(“%d%d%d%d” , &u , &v , &h , &w) ;if(h == -1) h = inf ;addedge(u , v , h , w) ;addedge(v , u , h, w) ;}scanf(“%d%d%d” , &st , &en , &lim) ;int ans = find(st , en ,lim) ;if(cas) puts(“”) ;printf(“Case %d:\n” , ++cas) ;if(ans < 0)puts(“cannot reach destination”);else{printf(“maximum height = %d\n” , ans) ;dijkstra(st , en , ans) ;printf(“length of shortest route = %d\n” , dis[en]) ;}}return 0 ;}

上一篇hdu5339Untitled 暴搜下一篇hdu5316Magician 线段树

顶0踩0

，只有流过血的手指才能弹出世间的绝唱。

相关文章：

你感兴趣的文章：

标签云：