1 /* 2 題意： 物主有一個物品，價值為P，地位為L， 以及一系列的替代品Ti和該替代品所對應的"優惠"Vi 3 g[u][i] 表示的是u物品被i物品替換后的優惠價格！(u>0, i>0) 4 g[u][0]表示不用替換該物品的實際價格 ！ 5 d[0]表示的是第一個物品經過一系列的物品替換之后的最少優惠價格！ 6 7 思路：每當我們通過Dijkstra算法得到離源點（1）最近的距離的節點 p的時候（也就是1...pre[p], p）這條 8 路徑上的物品互相替換后得到最優價格，我們需要判斷是否滿足路徑上的任意兩個節點的地位差的絕對值是否 9 <=m, 如果不是，那么這條路經就廢掉了！要從新找最短路！ 10 */ 11 #include<iostream> 12 #include<cstdio> 13 #include<cstring> 14 #include<algorithm> 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(p==1) 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(minP>L[pre[p]]) minP=L[pre[p]]; 34 if(maxP<L[pre[p]]) maxP=L[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 root=1; 44 int minLen, p; 45 46 for(int j=1; j<=n; ++j){ 47 minLen=INF; 48 for(int i=0; i<=n; ++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] && minLen>d[i]){ 55 minLen=d[i]; 56 p=i; 57 } 58 } 59 } 60 minP=maxP=L[p]; 61 if(p && !dfs(p)){//從路徑的地步往上走，看一下時候滿足條件 62 while(p!=1){ 63 d[p]=INF; 64 p=pre[p]; 65 } 66 j=0;//從頭開始尋找其他的路徑！ 67 root=1; 68 memset(vis, 0, sizeof(vis)); 69 vis[root]=1; 70 continue; 71 } 72 root=p; 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 i=1; i<=n; ++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

總結

以上是生活随笔為你收集整理的poj1062昂贵的聘礼（Dijkstra**）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。