题目大意:
小明从家里走到学校去考试, 路上有各个交叉点,它们有自己的海拔高度。 小明从家里走到学校的路上,必然会经过不同的交叉点,因此会不断的走上走下,忐忐忑忑,这让他很不安,会影响他考试的发挥。因此,他要选择一条起伏最小的路去学校。所谓的"起伏最小",是指这条路上海拔最高的点与海拔最低的点的差值最小。
在起伏最小的前提下,还要求出路程距离最短。
分析与总结:
这题让我想起以前做过的一题,HDU1598 ,不过那时是用最小生成树做的,而且那题只需要输出最小差而不用求最短路。
这题中,根据高度差的递增,明显满足条件的路径数量也是递增的,因此可以二分"高度差".
光有"高度差"还是不够的,因为"起伏值"等于最大高度减最小高度, 所以需要再枚举最小高度(下限low), 在根据最小高度+"高度差"得到最大高度(上限up), 有了low和up这两个条件,就可以进行求限制最短路。
做这题WA了有20+, 因为在求最短路时没有排除掉超过"上限"的边。
之后试着最小生成树的方法做了下,先求出"最小差"和上限与下限,然后再求最短路,但是WA了,纠结中…
代码:
二分+枚举+最短路
[cpp]
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int INF = 0x7fffffff;
const int VN = 120;
const int EN = 10005;
int n;
int m;
int size;
int head[VN];
int h[VN];
int order[VN];
int d[VN];