題干：

年輕的探險家來到了一個印第安部落里。在那里他和酋長的女兒相愛了，于是便向酋長去求親。酋長要他用10000個金幣作為聘禮才答應把女兒嫁給他。探險家拿不出這么多金幣，便請求酋長降低要求。酋長說："嗯，如果你能夠替我弄到大祭司的皮襖，我可以只要8000金幣。如果你能夠弄來他的水晶球，那么只要5000金幣就行了。"探險家就跑到大祭司那里，向他要求皮襖或水晶球，大祭司要他用金幣來換，或者替他弄來其他的東西，他可以降低價格。探險家于是又跑到其他地方，其他人也提出了類似的要求，或者直接用金幣換，或者找到其他東西就可以降低價格。不過探險家沒必要用多樣東西去換一樣東西，因為不會得到更低的價格。探險家現在很需要你的幫忙，讓他用最少的金幣娶到自己的心上人。另外他要告訴你的是，在這個部落里，等級觀念十分森嚴。地位差距超過一定限制的兩個人之間不會進行任何形式的直接接觸，包括交易。他是一個外來人，所以可以不受這些限制。但是如果他和某個地位較低的人進行了交易，地位較高的的人不會再和他交易，他們認為這樣等于是間接接觸，反過來也一樣。因此你需要在考慮所有的情況以后給他提供一個最好的方案。?
為了方便起見，我們把所有的物品從1開始進行編號，酋長的允諾也看作一個物品，并且編號總是1。每個物品都有對應的價格P，主人的地位等級L，以及一系列的替代品Ti和該替代品所對應的"優惠"Vi。如果兩人地位等級差距超過了M，就不能"間接交易"。你必須根據這些數據來計算出探險家最少需要多少金幣才能娶到酋長的女兒。?

Input

輸入第一行是兩個整數M，N（1 <= N <= 100），依次表示地位等級差距限制和物品的總數。接下來按照編號從小到大依次給出了N個物品的描述。每個物品的描述開頭是三個非負整數P、L、X（X < N），依次表示該物品的價格、主人的地位等級和替代品總數。接下來X行每行包括兩個整數T和V，分別表示替代品的編號和"優惠價格"。

Output

輸出最少需要的金幣數。

Sample Input

1 4 10000 3 2 2 8000 3 5000 1000 2 1 4 200 3000 2 1 4 200 50 2 0

Sample Output

5250

解題報告：

? ? ? ? 從1開始跑，多次跑最短路。

AC代碼：（這不是最優的板子。。。板子里沒有dis[minv] = minw;這句）

#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; const int INF = 0x3f3f3f3f; int maze[110][110]; int val[110],dis[110],rank[110]; bool vis[110]; bool ok[110]; int n; int Dijkstra() {memset(vis,0,sizeof(vis));memset(dis,INF,sizeof(dis));dis[1] = 0;int all = n;int minw,minv;while(all--) {minw = INF;for(int i = 1; i<=n; i++) {if(!vis[i] && dis[i] < minw &&ok[i]) {minv = i;minw = dis[i];}}if(minw == INF) break;//這里不一樣！！！ vis[minv] = 1;dis[minv] = minw;//emmm板子里沒有 后面這句for(int i = 1; i<=n; i++) {if(!vis[i] && dis[i] > dis[minv] + maze[minv][i] &&ok[i]) {dis[i] = dis[minv] + maze[minv][i];}}}int minn =INF;for(int i = 1; i<=n; i++) {if(dis[i] + val[i] < minn && vis[i]) {minn = dis[i] + val[i];}}return minn; }int main() {int limit,i,j,k,t;scanf("%d%d",&limit,&n);memset(dis,INF,sizeof(dis));memset(maze,INF,sizeof(maze));//就不初始化 //其實這個題是可以初始化0的 for ( i = 1; i <= n; i++ )maze[i][i] = 0;for(int i = 1; i<=n; i++) {scanf("%d",&val[i]);//val[i]一般代表點的價值，dis[i]一般代表出發點到該點的距離和 scanf("%d",&rank[i]);scanf("%d",&t);while(t--) {scanf("%d",&k);scanf("%d",&maze[i][k]);}}int ans = INF;for(int i = 0; i<=limit; i++) {memset(ok,0,sizeof(ok));for(int j = 1; j<=n; j++) {if(rank[j] >= rank[1]-(limit-i) && rank[j] <= rank[1]+i) ok[j] = 1;}ans = min(ans,Dijkstra());}printf("%d\n",ans);return 0 ; }

但是其中的Dijkstra函數：

int Dijkstra() {memset(vis,0,sizeof(vis));memset(dis,INF,sizeof(dis));dis[1] = 0;int all = n;int minw,minv;while(all--) {minw = INF;for(int i = 1; i<=n; i++) {if(!vis[i] && dis[i] < minw &&ok[i]) {minv = i;minw = dis[i];}} // if(minw == INF) break;//這里不一樣！！！ vis[minv] = 1;dis[minv] = minw;for(int i = 1; i<=n; i++) {if(!vis[i] && dis[i] > dis[minv] + maze[minv][i] &&ok[i]) {dis[i] = dis[minv] + maze[minv][i];}}}int minn =INF;for(int i = 1; i<=n; i++) {if(dis[i] + val[i] < minn && ok[i]) {minn = dis[i] + val[i];}}return minn; }

?這樣寫就wa，，不知道為啥。倆代碼一共就兩個地方不一樣。

---

我知道為什么wa了。你需要把這句刪掉，，板子里沒有這句。

總結：

? 1.以后還是把vis和dis的初始化放在DIjkstra里面吧，省的多次調用DIjkstra的時候忘了初始化。

? 2.一般用val[i]一般代表點的價值，dis[i]一般代表出發點到該點的距離和 。

? 3. 以后還是用鄰接表存圖吧，，maze初始化這地方有的時候是個坑，maze[i][i]這種情況是賦值0還是INF？

最后附一個dfs版本的：（https://blog.csdn.net/qq276291420/article/details/9470335）

#include<stdio.h> #include<string.h> int map[105][105]; int price[105]; int level[105]; int dis[105]; int n, m; int flag[105]; int min; int max_level, min_level; void dfs(int pos) {int i;int temp_max, temp_min;for(i = 2; i <= n; i++){if(map[pos][i] != -1 && flag[i] == 0){if(dis[pos] + map[pos][i] <= min){if(level[i] <= max_level && level[i] >= min_level){temp_max = max_level;temp_min = min_level;max_level = level[i] + m > max_level ? max_level : level[i] + m;min_level = level[i] - m > min_level ? level[i] - m : min_level;dis[i] = dis[pos] + map[pos][i];flag[i] = 1;dfs(i);flag[i] = 0;max_level = temp_max;min_level = temp_min;}}}}if(min > dis[pos] + price[pos])min = dis[pos] + price[pos]; } int main() { // freopen("test.txt", "r", stdin);while(scanf("%d %d", &m, &n), m + n != 0){ int p, l , x, t, v; int i, j;memset(map, -1, sizeof(map));memset(dis, 0, sizeof(dis));for(i = 1; i <= n; i++){scanf("%d %d %d", &p, &l, &x);level[i] = l;price[i] = p;for(j = 1; j <= x; j++){scanf("%d %d", &t, &v);map[i][t] = v;}}max_level = level[1] + m;min_level = level[1] - m;flag[1] = 1;min = price[1];dfs(1);printf("%d\n", min);}return 0; }

?

總結

以上是生活随笔為你收集整理的【POJ - 1062】【nyoj - 510】昂贵的聘礼 （Dijkstra最短路+思维）的全部內容，希望文章能夠幫你解決所遇到的問題。

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