题目大意：在等级差距的范围之内，用最少的金币换取酋长的答应。
解题思路：将每个物品看作是一个节点，每个节点包含2个值，这个节点所代表的物品的价值，这个物品的等级，
因为有些物品可能通过几种方式来换取，所以这不是树，而是一张图，一张永久静态图。
是图，还是静态的，那么就好办了。我们先可以不管接下去的步骤会是如何，先建图。
题目所求的最少金币，可以从图中看出来，它求的是物品1即节点1到其他点的最短距离，单源最短路径？
嗯！可以用dijkstra求，但是由于有等级的限制，导致要用dijkstra不止一次。所以用它写的话会有点麻烦
但可以一试。这里我用的是简单点的，用DFS写的。
下面讲解DFS解题步骤：
step 1: 建图；
2：写深搜函数， 因为有等级限制，所以深搜的范围也要有等级的限制。也就是说要用一个深搜函数把所有的可能全部搜出来。 又因为DFS解题的思路在于求出节点1到每个节点的路的总权值和再加上该点所代表的物品的价值。求出其中 最小的那个就是题目的解了。所以在深搜的时候还要传递一个路的总权值。而当遇到一个点时，就要看这个 点的等级，看他是不是与当前深搜的等级范围相符合，小于最小的等级，则还需判断是不是符合等级差，大于 最大的也是一样。如果都符合，则将范围扩大。在范围之间则等级范围差不变。继续对点深搜。
深搜的步骤：
S 1：从节点1搜起。范围则是节点1的等级到节点1的等级之间；搜索出与节点1相连的节点2；
2：将总权值加上节点2所代表的物品的价值，与最小值比，更新最小值。对点深搜。更新等级范围。
3：重复2步骤。
Source Code Problem: 1062 User: 201141919106 Memory: 216K Time: 0MS Language: C Result: Accepted Source Code #include <stdio.h> #include <stdlib.h> #include <string.h> #define N 101 #define INF 1234567890 typedef struct { int w; int d; } NVE; typedef struct { int map[N][N]; NVE p[N]; } graph; int vis[N]; int m,n,min; graph G; void init() { int i,l,k,num; memset(vis,0,sizeof(vis)); memset(G.map,-1,sizeof(G.map)); for(i=1; i<=n; i++) { scanf("%d%d%d",&G.p[i].w,&G.p[i].d,&num); while(num--) { scanf("%d%d",&k,&l); G.map[i][k]=l; } } } void dfs(int k,int min_rank,int max_rank,int value) { int i; vis[k]=1; if(value+G.p[k].w<min)min=value+G.p[k].w; for(i=1; i<=n; i++) { if(!vis[i]&&G.map[k][i]!=-1) { if(G.p[i].d<min_rank&&max_rank-G.p[i].d<=m) { dfs(i,G.p[i].d,max_rank,value+G.map[k][i]); } else if(G.p[i].d>max_rank&&G.p[i].d-min_rank<=m) { dfs(i,min_rank,G.p[i].d,value+G.map[k][i]); } else if(G.p[i].d<=max_rank&&G.p[i].d>=min_rank) dfs(i,min_rank,max_rank,value+G.map[k][i]); } } vis[k]=0; return ; } int main() { while(~scanf("%d%d",&m,&n)) { init();min=INF; dfs(1,G.p[1].d,G.p[1].d,0); printf("%d\n",min); } return 0; }
- 上一篇线性筛法求解 H数列问题
- 下一篇投递问题--图论--ACM算法