1062:昂贵的聘礼

聘礼"/>

1062:昂贵的聘礼

dijkstra, 单源最短路径
建图：
我们可以选取一个超级源点0（即虚拟源点 0 ），每个物品i自身的价格就相当于从顶点0到顶点i连一条边，每个物品i有多个可替代点就相当于从可替代点到顶点i连一条边，最终问题转化为求从顶点0到顶点1的最短路径。
参考：
AC代码：

//dijkstra, 单源最短路径
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;const int N = 110, INF = 0x3f3f3f3f;
int n, m;
int g[N][N], level[N],dis[N];
bool vis[N];int dijkstra(int down, int up) { // 等级区间[down, up]int i, j;memset(dis, INF, sizeof(dis));memset(vis, 0, sizeof(vis));dis[0] = 0;for (i = 1; i <= n; i++) {int tmp = -1;for(j = 0; j <= n; j++) {//找未访问点中距离最小的，if (!vis[j] && (tmp == -1 || dis[tmp] > dis[j]))tmp = j;}vis[tmp] = true;for (j = 0; j <= n; j++) {//更新距离if (level[j] >= down && level[j] <= up)dis[j] = min(dis[j], dis[tmp] + g[tmp][j]);}}return dis[1];
}int main() {int i;cin >> m >> n;// m地位等级差距限制, n物品的总数memset(g, INF, sizeof(g));// 初始化邻接矩阵   for (i = 1; i <= n; i++)g[i][i] = 0;for (i = 1; i <= n; i++) {int price, cnt;cin >> price>>level[i]>>cnt;g[0][i] =price; // 超级源点0到顶点i while (cnt--) {int id, cost;cin >> id >> cost;g[id][i] =cost;//可替代点id到顶点i}}int res = INF;for (i = level[1] - m; i <= level[1]; i++)//等级限制res = min(res, dijkstra(i, i + m));cout << res << endl;return 0;
}