重庆怎么做网站?,做新闻源网站采集站赚钱,高端网站有哪些,网站交互设计1 /*2 题意#xff1a; 物主有一个物品#xff0c;价值为P#xff0c;地位为L#xff0c; 以及一系列的替代品Ti和该替代品所对应的优惠Vi3 g[u][i] 表示的是u物品被i物品替换后的优惠价格#xff01;(u0, i0)4 g[u][0]表示不用替换该物品的… 1 /*2 题意 物主有一个物品价值为P地位为L 以及一系列的替代品Ti和该替代品所对应的优惠Vi3 g[u][i] 表示的是u物品被i物品替换后的优惠价格(u0, i0)4 g[u][0]表示不用替换该物品的实际价格 5 d[0]表示的是第一个物品经过一系列的物品替换之后的最少优惠价格6 7 思路每当我们通过Dijkstra算法得到离源点1最近的距离的节点 p的时候也就是1...pre[p], p这条8 路径上的物品互相替换后得到最优价格我们需要判断是否满足路径上的任意两个节点的地位差的绝对值是否9 m, 如果不是那么这条路经就废掉了要从新找最短路
10 */
11 #includeiostream
12 #includecstdio
13 #includecstring
14 #includealgorithm
15 #define INF 0x3f3f3f3f
16 using namespace std;
17
18 int g[105][105];
19
20 int d[105];
21 int L[105];
22 int vis[105];
23 int pre[106];
24 int m, n;
25 int minP, maxP;
26
27 bool dfs(int p){
28 if(p1) return true;
29 if(abs(minP-L[pre[p]])m || abs(maxP-L[pre[p]])m){
30 g[pre[p]][p]INF;//这条路径往回走的过程中如果发现某两个节点的地位差的绝对值m, 这一条边无效
31 return false; //注意不要改变其他路径的存在情况
32 }
33 if(minPL[pre[p]]) minPL[pre[p]];
34 if(maxPL[pre[p]]) maxPL[pre[p]];
35 return dfs(pre[p]);
36 }
37
38 void Dijkstra(){
39 memset(d, 0x3f, sizeof(d));
40 memset(vis, 0, sizeof(vis));
41 d[1]0;
42 vis[1]1;
43 int root1;
44 int minLen, p;
45
46 for(int j1; jn; j){
47 minLenINF;
48 for(int i0; in; i){
49 if(g[root][i]){
50 if(!vis[i] d[i]d[root]g[root][i]){
51 d[i]d[root]g[root][i];
52 pre[i]root;
53 }
54 if(!vis[i] minLend[i]){
55 minLend[i];
56 pi;
57 }
58 }
59 }
60 minPmaxPL[p];
61 if(p !dfs(p)){//从路径的地步往上走看一下时候满足条件
62 while(p!1){
63 d[p]INF;
64 ppre[p];
65 }
66 j0;//从头开始寻找其他的路径
67 root1;
68 memset(vis, 0, sizeof(vis));
69 vis[root]1;
70 continue;
71 }
72 rootp;
73 vis[root]1;
74 }
75 }
76
77
78 int main(){
79 while(scanf(%d%d, m, n)!EOF){
80 memset(g, 0x3f, sizeof(g));
81 for(int i1; in; i){
82 int p, x;
83 scanf(%d%d%d, p, L[i], x);
84 g[i][0]p;
85 while(x--){
86 int v, w;
87 scanf(%d%d, v, w);
88 g[i][v]w;
89 }
90 }
91 Dijkstra();
92 printf(%d\n, d[0]);
93 }
94 return 0;
95 } 转载于:https://www.cnblogs.com/hujunzheng/p/3925931.html
