http://acm.hdu.edu.cn/showproblem.php?pid=2363
题意:求最小高度差下的最短路
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <set>
//#include <map>
#include <queue>
#include <utility>
#include <iomanip>
#include <stack>
#include <list>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
//#include <ctime>
#include <ctype.h>
using namespace std;
#define LL __int64
#define inf 0x3fffffff
#define M 105
struct xxx{
int high;
int low;
}x[10005];
struct son{
int v;
int w;
};
vector<son> g[M];
int dist[M], n, H[M];
bool inq[M];
bool cmp (xxx a, xxx b)
{
return (a.high - a.low) < (b.high - b.low);
}
void spfa (int low, int high)
{
int i, v, w, u = 1;
for (i = 1; i <= n; i++)
{
dist[i] = inf;
inq[i] = false;
}
queue<int> q;
q.push (u);
dist[u] = 0;
inq[u] = true;
while (!q.empty())
{
u = q.front();
q.pop();
inq[u] = false;
if (H[u] < low || H[u] > high) //起点也要限制
continue;
for (i = 0; i < g[u].size(); i++)
{
v = g[u][i].v;
if (H[v] < low || H[v] > high) //高度的限制
continue;
w = g[u][i].w;
if (dist[u] + w < dist[v])
{
dist[v] = dist[u] + w;
if (!inq[v])
{
q.push (v);
inq[v] = true;
}
}
}
}
}
int main()
{
int t, m, u, v, w, i, j, k;
son s;
scanf ("%d", &t);
while (t--)
{
scanf ("%d%d", &n, &m);
for (i = 1; i <= n; i++)
{
scanf ("%d", H+i);
g[i].clear();
}
k = 0;
for (i = 1; i <= n; i++)
{
for (j = i; j <= n; j++) //不能写成j=i+1,想想起点=终点的情况
{
x[k].low = min (H[i], H[j]);
x[k++].high = max (H[i], H[j]);
}
}
while (m--)
{
scanf ("%d%d%d", &u, &v, &w);
s.v = v;
s.w = w;
g[u].push_back (s);
s.v = u;
g[v].push_back (s);
}
sort (x, x+k, cmp); //按差排序
for (i = 0; i < k; i++) //差从小到大暴力枚举
{
spfa (x[i].low, x[i].high);
if (dist[n] != inf) //一旦可到达,立刻得出答案
break;
}
printf ("%d %d\n", x[i].high-x[i].low, dist[n]);
}
return 0;
}