首页 > 代码库 > hdu 2363

hdu 2363

枚举加最短路

#include <stdio.h>#include <string.h>#include <algorithm>#include <queue>using namespace std;#define N 105#define INF 0x7f7f7f7fstruct Height{    int low,high,dif;}H[N*N];struct Edge{    int u ,val,next;}e[N*N];int h[N],p[N],vis[N],d[N],n;bool cmp(Height a,Height b){    return a.dif<b.dif;}void add(int n,int m){    int i,x,y,val,cout = 1;    for(i = 1 ; i <= n ; i++) p[i] = -1;    while(m--)    {        scanf("%d %d %d",&x,&y,&val);        e[cout].u = y;        e[cout].val = val;        e[cout].next = p[x];        p[x] = cout++;        e[cout].u = x;        e[cout].val = val;        e[cout].next = p[y];        p[y] = cout++;    }}int spfa(Height temp){    int i;    memset(vis,0,sizeof(vis));    for(i = 1 ; i <= n ; i++) d[i] = INF;    queue<int>q;    vis[1] = 1;    d[1] = 0;    q.push(1);    while(!q.empty())    {        int cur = q.front();        q.pop();        if(h[cur]<temp.low||h[cur]>temp.high) continue;        for(i = p[cur] ; i != -1 ; i = e[i].next)        {            if(d[e[i].u]>d[cur]+e[i].val && h[e[i].u]>=temp.low&&h[e[i].u]<=temp.high)            {                d[e[i].u] = d[cur] +e[i].val;                if(!vis[e[i].u])                {                    vis[e[i].u] = 1;                    q.push(e[i].u);                }            }        }        vis[cur] = 0;    }    return d[n];}int main(){    int t,m,x,y,val,i,j;    scanf("%d",&t);    while(t--)    {        scanf("%d %d",&n,&m);        for(i = 1 ; i <= n ; i++)            scanf("%d",&h[i]);        add(n,m);        int k = 0;        for(i = 1 ; i <= n ; i++)        {            for(j = i ; j <= n ; j++)            {                H[k].high = max(h[i],h[j]);                H[k].low = min(h[i],h[j]);                H[k].dif = H[k].high - H[k].low;                k++;            }        }        sort(H,H+k,cmp);        int ans;        for(i = 0 ; i < k ; i++)        {            ans = spfa(H[i]);            if(ans != INF) break;        }        printf("%d %d\n",H[i].dif,ans);    }}