题目链接：
http://poj.org/problem?id=1062
题目意思：
中文题目，我就不再废话了。但是有一点要提醒的是在整个交易网中，参加交易的人的最高级别和最低级别差不能超过m，而不是与相邻交易的级别差不超过m，经过一下午的纠结以后，血淋淋的教训告诉我们以后读题目一定要认真，写代码之前要思考，思考时候要慎重。
解题思路：
本题最重要的是要想清楚怎么建造图更合适。
1：我们可以建造一个0点代表虚拟的原点，把1当成终点，以此转化为求到1的最短路。
2：交换是有方向的，只能单向交换，要建立有向图。
3：一个合法的交易链中，级别最高级别和最低级别差别不能超过m。
4：起点不能确定，所以要枚举比较得出最短。
1 #include <cmath> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 #include <iostream> 7 using namespace std; 8 #define maxn 110 9 #define INF 0x3f3f3f3f 10 11 struct node 12 { 13 int val[maxn];//可以与之交换的物品的价格 14 int num[maxn];//可以与之交换的物品的编号 15 int p, l, x; 16 }goods[maxn]; 17 18 int map[maxn][maxn], n, m; 19 void init (); 20 int dijk (int x);//用dijkstra求最短路 21 22 int main () 23 { 24 int i, j; 25 while (scanf ("%d %d", &m, &n) != EOF) 26 { 27 init (); 28 memset (goods, 0, sizeof(goods)); 29 for (i=1; i<=n; i++) 30 { 31 scanf ("%d %d %d", &goods[i].p, &goods[i].l, &goods[i].x); 32 map[0][i] = goods[i].p;//设定一个虚拟的原点，避免所建图中没有边，无法进行计算 33 for (j=0; j<goods[i].x; j++) 34 scanf ("%d %d", &goods[i].num[j], &goods[i].val[j]); 35 } 36 for (i=1; i<=n; i++) 37 for (j=0; j<goods[i].x; j++) 38 if (abs(goods[goods[i].num[j]].l - goods[i].l) <= m && map[goods[i].num[j]][i] > goods[i].val[j]) 39 {//在合法的等级范围内建边，并且尽量建立最短的边 40 map[goods[i].num[j]][i] = goods[i].val[j]; 41 } 42 43 int mi = INF; 44 for (i=1; i<=n; i++)//对所有有效的等级进行遍历 45 mi = min (mi, dijk(i)); 46 printf ("%d ", mi); 47 } 48 return 0; 49 } 50 51 void init () 52 { 53 int i, j; 54 for (i=0; i<=n; i++) 55 for (j=0; j<=n; j++) 56 map[i][j] = INF; 57 } 58 59 int dijk (int x) 60 { 61 int dist[maxn], vis[maxn], i, j; 62 int high = goods[x].l + m;//等级最大值 63 int low = goods[x].l;//等级最小值 64 memset (vis, 0, sizeof(vis)); 65 for (i=0; i<=n; i++)//在有效等级内初始化为有效值，否则为INF 66 if (low <= goods[i].l && goods[i].l <= high) 67 dist[i] = map[0][i]; 68 else 69 dist[i] = INF; 70 71 vis[0] = 1; 72 73 for (j=0; j<n; j++) 74 { 75 int mi = INF, index; 76 for (i=0; i<=n; i++) 77 {//因为无效等级的dist为INF，不需要对点的等级判断 78 if (!vis[i] && dist[i] < mi) 79 { 80 mi = dist[i]; 81 index = i; 82 } 83 } 84 if (mi == INF) 85 break;//图中各点有可能不是联通的，会造成下一步数组越界 86 vis[index] = 1; 87 88 for (i=0; i<=n; i++)//加入最优点以后，对现有边进行松弛 89 if (!vis[i] && low<=goods[i].l && goods[i].l <=high && map[index][i] + dist[index] < dist[i]) 90 dist[i] = dist[index] + map[index][i]; 91 } 92 return dist[1]; 93 }