903 昂贵的聘礼（单源最短路径-建图）

2. 思路分析：

分析题目可以知道这道题目的背景还是挺复杂的，所以我们首先需要弄清楚题目的意思，捋清楚其中的逻辑关系，弄清楚要求的是什么，对于这种比较复杂的题目，我们可以先在纸上画一下其中节点与节点之间的联系，看是否可以将其抽象为一个图论的模型，我们可以从简单一点的问题搞起，暂时先不考虑等级的限制，等到我们已经捋清楚了题目的逻辑关系再考虑等级的限制，以题目中的测试用例为例画出物品与物品之间的关系如下图所示，这样我们就将题目中的关系转换为了图论的简单模型，所以离建图又进了一步：

因为求解花费最少的金币，所以属于最短路径问题，我们可以考虑一下起点和终点，终点其实很好确定，为题目中的1号点，关键是起点，因为题目肯定是有解的（最终可以使用金币来买物品），所以起点肯定是买一个物品，最终通过中间的若干个点转移到1号点，所以我们其实可以建一个虚拟源点(虚拟源点是核心)，虚拟源点到其余点表示直接买当前的物品需要花费的金币数目，因为题目中的节点编号是从1~N的，所以0号点可以设置为虚拟源点，虚拟源点到其余点的边表示买这个商品需要花费的金币数目，其余的点与点之间的边表示通过得到某个商品外加对应的金币那么就可以得到另外的的物品，在图中可以表示为向另外一个点连一条边，最终我们就将原问题转换为了最短路径问题，我们只需要求解从虚拟源点0出发到编号为1的终点的最短路径即可。可以发现题目的难点是如何将问题抽象为图论中的模型。捋清楚题目的逻辑关系之后，还有一个等级限制的问题，其实我们枚举所有合法的区间，题目规定了最小等级与最大等级的差值要小于等于M，所以每一次我们需要以1号点的等级为标准，枚举一个区间，判断对应的节点是否在这个区间之内，如果在这个区间说明可以更新最短路径，求解最短路径的时候使用任何一种最短路径的算法即可，下面使用的是朴素版本的解法。

3. 代码如下：

邻接矩阵：

from typing import Listclass Solution:# n表示图中点的个数, down表示区间等级的最小值, up表示区间等级的最大值, w表示有向图def dijkstra(self, n: int, down: int, up: int, level: List[int], w: List[List[int]]):INF = 10 ** 9dis = [INF] * (n + 1)dis[0] = 0vis = [0] * (n + 1)for i in range(n):k = -1for j in range(n + 1):if vis[j] == 0 and (k == -1 or dis[k] > dis[j]):k = jvis[k] = 1for j in range(1, n + 1):# 判断节点是否在等级区间内if down <= level[j] <= up:dis[j] = min(dis[j], dis[k] + w[k][j])return dis[1]def process(self):m, n = map(int, input().split())INF = 10 ** 9# 使用邻接矩阵存储w = [[INF] * (n + 1) for i in range(n + 1)]level = [0] * (n + 1)for i in range(1, n + 1):t = list(map(int, input().split()))# 0向第i个点连一条边(源点向其他点连一条边)w[0][i] = t[0]level[i] = t[1]count = t[2]for j in range(count):idx, price = map(int, input().split())# 其余点向第i个点连一条边(根据图确定哪一个在前哪一个在后)w[idx][i] = min(w[idx][i], price)res = INF# 枚举等级区间, 注意题目的意思是最高等级与最低等级的差要小于等于Mfor i in range(level[1] - m, level[1] + 1):res = min(res, self.dijkstra(n, i, i + m, level, w))return resif __name__ == "__main__":print(Solution().process())

邻接表：

from typing import Listclass Solution:def dijkstra(self, n: int, down: int, up: int, level: List[int], g: List[dict]):INF = 10 ** 9dis = [INF] * (n + 1)dis[0] = 0vis = [0] * (n + 1)for i in range(n):k = -1# 注意循环的时候是从0开始的                    for j in range(n + 1):if vis[j] == 0 and (k == -1 or dis[k] > dis[j]):k = jvis[k] = 1for next in g[k].items():if down <= level[next[0]] <= up:dis[next[0]] = min(dis[next[0]], dis[k] + next[1])return dis[1]def process(self):# m为等级限制m, n = map(int, input().split())# 每一个g[i]是一个字典就相当于是一个邻接表g = [dict() for i in range(n + 1)]level = [0] * (n + 1)for i in range(1, n + 1):p, l, count= map(int, input().split())g[0][i] = plevel[i] = lfor j in range(count):idx, price = map(int, input().split())if i in g[idx]:g[idx][i] = min(g[idx][i], price)else: g[idx][i] = priceINF = 10 ** 9res = INFfor i in range(level[1] - m, level[1] + 1):res = min(res, self.dijkstra(n, i, i + m, level, g))return res                if __name__ == "__main__":print(Solution().process())