hdu2363Cycling 二分+最短路

分类：最短路二分

二分-最短路

//一个无向图，每个点都有高度，，//问从起点1到终点n的最高点减最低点的差值最小的前提下的最短路和这个差值//由于n<using namespace std ;const int maxn = 110 ;const int maxm = 5010 ;const int inf = 0x3f3f3f3f ;struct Edge{int v ,w ;int next ;}edge[maxm<<1] ;int n , m ;int head[maxn] , vis[maxn] , dis[maxn] , h[maxn] , a[maxn];int nedge ;void addedge(int u , int v , int w){edge[nedge].v = v ;edge[nedge].w = w ;edge[nedge].next = head[u] ;head[u] = nedge++ ;}bool dijkstra(int mi , int ma){if(h[1] < mi || h[1] > ma) return false ;for(int i = 2;i <= n;i++)dis[i] = inf ;dis[1] = 0 ;memset(vis , 0 , sizeof(vis)) ;while(1){int mi_1 = inf, pos ;for(int i = 1; i <= n ;i++)if(!vis[i] && dis[i] < mi_1)mi_1 = dis[pos = i] ;if(mi_1 == inf)break;vis[pos] = 1 ;for(int i = head[pos] ; i != -1 ;i = edge[i].next){int v = edge[i].v ;if(h[v] < mi || h[v] > ma)continue ;if(dis[v] > dis[pos] + edge[i].w)dis[v] = dis[pos] + edge[i].w ;}}if(dis[n] == inf)return false ;else return true ;}int find(int l , int r){int pos = l ;while(l <= r){int mid = (l + r) >> 1 ;if(!dijkstra(a[pos] , a[mid]))l = mid + 1 ;else r = mid – 1;}return l ;}int main(){//freopen(“in.txt” ,”r” , stdin) ; // freopen(“out.txt” ,”w” ,stdout) ;int t ;scanf(“%d” , &t) ;while(t–){scanf(“%d%d” , &n , &m) ;memset(head , -1 , sizeof(head)) ;nedge = 0 ;for(int i = 1;i <= n;i++){scanf(“%d” , &h[i]) ;a[i] = h[i] ;}sort(a + 1 , a + 1 + n);int len_a = unique(a + 1 , a + 1 + n) – a ;while(m–){int u , v , w ;scanf(” , &u ,&v , &w) ;addedge(u , v , w) ;addedge(v , u , w) ;}int mi = 0 , ma = inf , len = inf ;for(int i = 1;i <= len_a;i++){if(a[i] > h[1])break;int r = find(i , len_a) ;if(r <= len_a){if(a[r] – a[i] < ma – mi){dijkstra(a[i] , a[r]) ;mi = a[i] , ma = a[r] , len = dis[n] ;}if(a[r] – a[i] == ma – mi){dijkstra(a[i] , a[r]) ;if(dis[n] < len)mi = a[i] , ma = a[r] , len = dis[n] ;}}}printf(“%d %d\n” , ma – mi , len) ;}return 0 ;}

上一篇hdu5316Magician 线段树下一篇hdu3768Shopping 最短路+暴力

顶0踩0

真凉爽啊！青山绿水映入我的眼中，景色怡人啊！

相关文章：

你感兴趣的文章：

标签云：