每个点有一个高度,从1到n使得最大高度和最小高度的差值最小,如果有相同高度,取路径最短的。以前比赛的时候没有去看,以为是很难的题,后来听说要用二分,一直拖着,今天早上起来,读了一下题目发现根本不用二分,点只有100个,可以对每个点的高度进行上下界枚举求最短路保存最优值。这样的话最坏复杂度是O(n^4),这里n == 100,而且测试样例有100组,但是这个题目的限制条件决定了有很多地方可以剪枝。首先,可以先将每个点的高度进行升序排列,如果1或n不在所枚举的高度上下界中,直接跳过。再者,如果当前枚举的高度差大于先前算出来的最优值,直接跳过不算,最强的是:如果当前能够算出解,那么上界再大亦可算出,直接break;
代码如下:
#include <iostream>
#include <algorithm>
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int t;
int alti[101];
int n, m;
int d[101], s[101];
int map[101][101];
int sor[101];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int Dijkstra(int Min, int Max)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int i;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i = 1; i <= n; i++)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(alti[i] > Max || alti[i] < Min)
{
d[i] = 100000000;
s[i] = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
}else
{
d[i] = map[1][i];
s[i] = 0;
}
}
d[1] = 0;
s[1] = 1;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(1)
{
int Mina = 100000000, u = -1;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i = 1; i <= n; i++)
{
if(alti[i] > Max || alti[i] < Min)
continue;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(!s[i] && d[i] < Mina)
{
Mina = d[i];
u = i;
}
}
if(u == n)
return d[u];
if(u == -1)
return -1;
s[u] = 1;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i = 1; i <= n; i++)
{
if(alti[i] > Max || alti[i] < Min)
continue;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(!s[i] && d[u] + map[u][i] < d[i])
{
d[i] = d[u] + map[u][i];
}
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int i, j;
scanf("%d", &t);
int a, b, c;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(t--)
{
scanf("%d %d", &n, &m);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i = 1; i <= n; i++)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(j = 1; j <= n; j++)
{
map[i][j] = 100000000;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i = 1; i <= n; i++)
{
scanf("%d", &alti[i]);
sor[i-1] = alti[i];
}
sort(sor, sor + n);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(m--)
{
scanf("%d %d %d", &a, &b, &c);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(c < map[a][b])
{
map[a][b] = map[b][a] = c;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int Min = 2000000000, path;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i = 0; i < n; i++)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(j = i+1; j < n; j++)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(alti[n] > sor[j] || alti[n] < sor[i])
continue;
if(alti[1] > sor[j] || alti[1] < sor[i])
continue;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(sor[j] - sor[i] > Min)
break;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int yu;
yu = Dijkstra(sor[i], sor[j]);
//printf("%d %d %d\n", sor[i], sor[j], yu);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(yu + 1 && sor[j] - sor[i] == Min)
{
if(yu < path)
path = yu;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(yu + 1 && sor[j] - sor[i] < Min)
{
Min = sor[j] - sor[i];
path = yu;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(yu != -1)
break;
}
}
if(n == 1)
printf("0 0\n");
else
printf("%d %d\n", Min, path);
}
}