单源最短路的虚拟点应用

1. 对于想要购买的物品，要么直接购买，要么通过其他物品进行百亿补贴

2. 通过其他物品购买的过程实际上就是一个建立关系的过程，可以联想到图论问题

3. 对于目标物品直接购买或者中间物品的直接购买，我们利用建立一个0号虚拟节点，从该点出发即可走到所有点，遍历所有边，与其直接连接的路程为商品原价

4. 完成虚拟节点和其他节点直接相互的建边后，进行最短路

5. 最短路过程种，需要加入等级条件，我们暴力所有等级条件，求最优解即可

python版本

推销一下下面的个人发明建边函数def Lin(a,b,c)（我称之为琦氏建边法），速度虽然比纯append来的慢，但是可以稳定的去重边和取最优重边，给用python写图论的兄弟们安利一下=_+

#  本题主要考察单源最短路中虚拟节点的使用以及添加了一个松弛条件（这里我用SPFA）
#SPFA算法
def Lin(a,b,c):
    if a not in link.keys():
        link[a] = {b:c}
    else:
        if b not in link[a].keys():
            link[a].update({b:c})
        else:
            link[a][b] = max(link[a][b],c)

def SPFA(down_L,up_L):
    queue = [0]
    inq = [False]*(n+1)  #判断是否在队列中
    dis = [float('inf')]*(n+1)
    dis[0] = 0
    inq[0] = True     #这是优化点，避免重复入队
    while queue:

        sam = queue.pop(0)
        inq[sam] = False

        if sam not in link.keys():
            continue

        for node in link[sam]:
            if level[node] < down_L or level[node] > up_L: #等级在范围内才更新
                continue
            if dis[node] > dis[sam] + link[sam][node]:
                dis[node] = dis[sam] + link[sam][node]
                if inq[node] == True:  #如果在队列中则不管他
                    continue
                inq[node] = True
                queue.append(node)

    return dis[1]


m,n = map(int,input().split())
level = [0]*(n+1)
link = {}
link[0] = {}
for i in range(1,n+1):
    P,L,X = map(int,input().split())
    level[i] = L
    link[0].update({i:P}) #利用虚拟节点对原物品建边表示原价购买
    for j in range(X):  #对替代品和目标之间建边
        node,cost = map(int,input().split())
        Lin(node,i,cost)

res = float('inf')
for i in range(level[1] - m,level[1] + 1):
    res = min(res,SPFA(i,m+i))
print(res)