[题目来源]：POJ 1062
[关键字]：最短路径 枚举
[题目大意]：n件物品，每件物品有一个价值和登记，可以直接买也可以通过买别的东西再交换来优惠，但等级向差n的两间物品无能进行交换。问买到1物品的最小花费。
//================================================================================================
[分析]：首先将问题简化：不考虑等级限制。很简单，将能物品x与需要它来优惠的物品y间连一条权为优惠价的有向边，然后将所有物品初值都赋为其本身价值，然后SPFA即可。现在有了等级限制怎么办？我们可以枚举等级区间，以一件物品的等级作为区间上界，则凡满足：0<=l[st]-l[i]<=m（st是枚举的上界）的点都选入，然后按刚才所说SPFA，最后取f[1]最小的值。注意此处不一定是以酋长作为区间上界或起点因为酋长不一定最高或最低，若以其为上（下）界，则少了等级处于酋长两边的物品处于同一区间的状态。
//=================================================================================================
[代码]：
C++ #include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<set> using namespace std; const int MAXN=110; const int INF=0x7fffffff; int S,n,m,tot; int a[MAXN][MAXN],level[MAXN],L[MAXN],d[MAXN]; bool v[MAXN]; set<int> SET; void Init() { scanf("%d%d",&m,&n); S=0; memset(a,100,sizeof(a)); for (int i=1;i<=n;++i) { int x,y,z; scanf("%d%d%d",&x,&y,&z); a[S][i]=x,level[i]=y; if (SET.find(y)==SET.end() || SET.empty()) L[++tot]=y,SET.insert(y); for (int j=1;j<=z;++j) { scanf("%d%d",&x,&y); a[x][i]=y; } } /*for (int i=0;i<=n;++i) { for (int j=0;j<=n;++j) printf("%d ",a[i][j]); printf("\n"); }*/ } int Dij(int st,int x) { memset(d,100,sizeof(d)); memset(v,0,sizeof(v)); d[st]=0; //printf("%d\n",L[x]); for (int i=0;i<=n;++i) { int Min=INF,Minj=-1; for (int j=0;j<=n;++j) if (!v[j] && (j==S || (L[x]<=level[j] && level[j]<=m+L[x])) && Min>d[j]) Min=d[Minj=j]; v[Minj]=1; //printf("%d ",Minj); for (int j=0;j<=n;++j) if (!v[j] && (j==S || (L[x]<=level[j] && level[j]<=m+L[x])) && d[j]>d[Minj]+a[Minj][j]) d[j]=d[Minj]+a[Minj][j]; } return d[1]; } void Solve() { int ans=INF; sort(L+1,L+1+tot); //for (int i=1;i<=n;++i) printf("%d ",level[i]); //printf("\n"); for (int i=1;i<=tot;++i) { int temp=Dij(S,i); //printf("%d\n",temp); if (temp<ans) ans=temp; } printf("%d\n",ans); } int main() { Init(); Solve(); return 0; } View Code 1 type 2 rec = record 3 y, d, n: longint 4 end; 5 var 6 tot, n, m: longint; 7 e: array[0..2000] of rec; 8 link: array[0..200] of longint; 9 v, l, d: array[0..200] of longint;10 b: array[0..200] of boolean;11 q: array[0..2000] of longint;12 13 procedure make(x, y, d: longint);14 begin15 inc(tot);16 e[tot].y := y;17 e[tot].d := d;18 e[tot].n := link[x];19 link[x] := tot;20 end;21 22 procedure init;23 var24 i, j, t, y, d: longint;25 begin26 readln(m,n);27 for i := 1 to n do28 begin29 read(v[i],l[i],t);30 for j := 1 to t do31 begin32 read(y,d);33 make(y,i,d);34 end;35 end;36 end;37 38 function spfa(st: longint): longint;39 var40 h, t, temp, x, y, i: longint;41 begin42 h := 1;43 t := 0;44 fillchar(b,sizeof(b),false);45 fillchar(d,sizeof(d),100);46 for i := 1 to n do47 if (l[st]-l[i] >= 0) and (l[st]-l[i] <= m) then48 begin49 inc(t);50 q[t] := i;51 d[i] := v[i];52 b[i] := true;53 end;54 while h <= t do55 begin56 x := q[h];57 temp := link[x];58 while temp > 0 do59 begin60 y := e[temp].y;61 if (l[st]-l[y] >= 0) and (l[st]-l[y] <= m) then62 if d[y] > d[x]+e[temp].d then63 begin64 d[y] := d[x]+e[temp].d;65 if not b[y] then66 begin67 inc(t);68 q[t] := y;69 b[y] := true;70 end;71 end;72 temp := e[temp].n;73 end;74 b[x]:= false;75 inc(h);76 end;77 exit(d[1]);78 end;79 80 procedure work;81 var82 i, ans, temp: longint;83 begin84 ans := maxlongint;85 for i := 1 to n do86 begin87 temp := spfa(i);88 if ans > temp then ans := temp;89 end;90 writeln(ans);91 end;92 93 begin94 init;95 work;96 end.转载于:https://www.cnblogs.com/procedure2012/archive/2011/10/15/2213716.html
相关资源：poj 1062 昂贵的聘礼 代码