【枚举+最短路】HDU 2363 Cycling

基德KID.1412

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 105struct 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 = inf;        inq = false;    }    queue<int> q;    q.push (u);    dist = 0;    inq = true;    while (!q.empty())    {        u = q.front();        q.pop();        inq = false;        if (H < low || H > high)    //起点也要限制            continue;        for (i = 0; i < g.size(); i++)        {            v = g.v;            if (H[v] < low || H[v] > high)    //高度的限制                continue;            w = g.w;            if (dist + w < dist[v])            {                dist[v] = dist + 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.clear();        }        k = 0;        for (i = 1; i <= n; i++)        {            for (j = i; j <= n; j++)    //不能写成j=i+1，想想起点=终点的情况            {                x[k].low = min (H, H[j]);                x[k++].high = max (H, H[j]);            }        }        while (m--)        {            scanf ("%d%d%d", &u, &v, &w);            s.v = v;            s.w = w;            g.push_back (s);            s.v = u;            g[v].push_back (s);        }        sort (x, x+k, cmp);        //按差排序        for (i = 0; i < k; i++)    //差从小到大暴力枚举        {            spfa (x.low, x.high);            if (dist[n] != inf)    //一旦可到达，立刻得出答案                break;        }        printf ("%d %d\n", x.high-x.low, dist[n]);    }    return 0;}