題目分析

來源：acwing

由于終點是1號節點，建立虛擬節點S，如下建圖（根據樣例畫圖）。S出發和每個點直連的邊權代表直接買該物品花的金幣數；而由S到1的任意一條通路，邊權之和就是花費的金幣數。所以，此題就是求從S到1的最短距離。

那么等級限制怎么做呢？暴力枚舉。在dijkstra算法中，傳入的參數是（合理等級最低，合理等級最高），而且在更新距離時，需要滿足等級條件。

#include<bits/stdc++.h> using namespace std; const int N = 110, INF = 0x3f3f3f3f; int n, m; int w[N][N],level[N]; int dist[N]; bool st[N];int dijkstra(int down, int up){memset(dist, 0x3f, sizeof dist);memset(st, 0, sizeof st);dist[0] = 0;for(int i = 1; i <= n; i ++){int t = -1;for(int j = 0; j <= n; j ++)if(!st[j] && (t == -1 || dist[t] > dist[j]))t = j;st[t] = true;for(int j = 1; j <= n; j ++)//等級合法的時候才更新if(level[j] >= down && level[j] <= up)dist[j] = min(dist[j], dist[t] + w[t][j]);}return dist[1]; }int main(){cin >> m >> n;memset(w, 0x3f, sizeof w);for(int i = 1; i <= n; i++) w[i][i] = 0;for(int i = 1; i <= n; i ++){int price ,cnt;cin >> price >> level[i] >> cnt;// 由虛擬源點到這個點連一條邊w[0][i] = min(w[0][i], price);while(cnt --){int id , cost;cin >> id >> cost;w[id][i] = min(w[id][i], cost);}}int res = INF;// 枚舉等級的最小值，只能在1號點的合理范圍內for(int i = level[1] - m; i <= level[1]; i++) res = min(res, dijkstra(i, i + m)); // 傳入的是等級范圍cout << res << endl;}

題目來源

https://www.acwing.com/problem/content/905/

總結

以上是生活随笔為你收集整理的算法提高课-图论-单源最短路的建图方式-AcWing 903. 昂贵的聘礼：建图巧妙、dijkstra、考虑等级的全部內容，希望文章能夠幫你解決所遇到的問題。

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