百练OJ-昂贵的聘礼

思路：

输入n个结点，手动添加一个n+1结点，n+1节点到i节点的距离代表直接购买物品的花费，从j结点到k节点的距离代表物品k用j换的花费。输入数据时候判断物品的等级是否在酋长等级的【+-m】内，在的话才添加，不然就还是inf。dijkstra内更新距离时判断和之前所有添加过的点的等级与最小点等级的差是否满足条件。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#define inf 0x3f3f3f3f
using namespace std;
int m, n;
int edges[111][111];
int rootl;
int dis[111];
bool vis[111];
map<int, int>mymap;
vector<int>vec;
void dijkstra() {memset(dis, inf, sizeof(dis));vec.clear();for (int i = 1; i <= n + 1; i++) {dis[i] = edges[n + 1][i];}vis[n + 1] = true;vec.push_back(n + 1);for (int i = 1; i <n+1; i++) {int min_ = inf;int v=-1;for (int j = 1; j <= n + 1; j++) {if (!vis[j] && min_ > dis[j]) {min_ = dis[j];v = j;}}if (v == -1)break;vis[v] = true;vec.push_back(v);for (int j = 1; j <= n + 1; j++) {if (!vis[j]) {bool fg = true;for (int k = 0; k < vec.size(); k++) {if (abs(mymap[vec[k]] - mymap[j]) > m) {fg = false;break;}}if(fg)dis[j] = min(dis[j], dis[v] + edges[v][j]);}}}cout << dis[1] << endl;
}
int main() {while (cin >> m >> n) {mymap.clear();memset(edges, inf, sizeof(edges));memset(vis, false, sizeof(vis));for (int i = 1; i <= n + 1; i++) {edges[i][i] = 0;}for (int i = 1; i <= n; i++) {int p, l, x;cin >> p >> l >> x;mymap[i] = l;if (i == 1) {rootl = l;mymap[n + 1] = l;}if (abs(rootl - l) <= m){	edges[n + 1][i] = p;}for (int j = 0; j < x; j++) {int t, v;cin >> t >> v;if (abs(rootl - l) <= m)edges[t][i] = v;}}dijkstra();}return 0;
}

1. 测试数据1:  
2. 1 4  
3. 10000 3 2  
4. 2 8000  
5. 3 5000  
6. 1000 2 1  
7. 4 200  
8. 3000 2 1  
9. 4 200  
10. 50 2 0  
11.   
12. 5250  
13.   
14. 测试数据2:  
15. 1 5  
16. 10000 3 4  
17. 2 3000  
18. 3 2000  
19. 4 2000  
20. 5 9000  
21. 8000 2 3  
22. 3 5000  
23. 4 2000  
24. 5 7000  
25. 5000 1 0  
26. 2000 4 1  
27. 5 1900  
28. 50 1 0  
29.   
30. 4000  
31. 测试数据3:  
32. 3 8  
33. 10000 3 6  
34. 2 3000  
35. 3 2000  
36. 4 2000  
37. 5 9000  
38. 7 1000  
39. 8 5008  
40. 8000 2 3  
41. 3 5000  
42. 4 2000  
43. 5 7000  
44. 5000 1 1  
45. 6 1000  
46. 2000 4 1  
47. 5 1900  
48. 50 1 0  
49. 5000 1 1  
50. 7 4007  
51. 2000 4 1  
52. 5 1900  
53. 80 3 0  
54.   
55. 2950  
56. 测试数据4:  
57. 1 10  
58. 1324 0 0  
59. 1234 0 0  
60. 255 0 0  
61. 67 0 0  
62. 56 0 0  
63. 2134 0 0  
64. 456 0 0  
65. 2345 0 0  
66. 67 0 0  
67. 6436 0 0  
68.   
69. 1324  
70.   
71. 测试数据5:  
72. 1 4  
73. 10000 3 2  
74. 2 1  
75. 3 3  
76. 1000 2 2  
77. 4 1  
78. 3 1  
79. 1000 3 1  
80. 4 2  
81. 100 4 0  
82.   
83. 105  
84. 测试数据6:  
85. 3 5  
86. 10000 3 4  
87. 2 3000  
88. 3 2000  
89. 4 2000  
90. 5 9000  
91. 8000 2 3  
92. 3 5000  
93. 4 2000  
94. 5 7000  
95. 5000 1 0  
96. 2000 4 1  
97. 5 1900  
98. 50 1 0  
99.   
100. 3950