首页 > 代码库 > 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); }}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。