题目描述
J想要创造n种魔法宝石。J可以用ai的魔力值创造一出第 i 种魔法宝石，或是使用两个宝石合成另一种宝石（不消耗魔力值）。请你帮J算出合成某种宝石的所需的最小花费。
输入
首先一行为n,m(1≤n,m≤10^5)。分别表示魔法宝石种类数和合成魔法的数量。
之后一行n个数表示a1到an。(1≤ai≤10^9)。a_i表示合成第i种宝石所需的魔力值。
之后n行，每行三个数a,b,c(1≤a,b,c≤n),表示一个第a种宝石和第b种宝石，可以合成一个第c种宝石。
输出
每组数据输出一行n个数，其中第i个数表示合成第i种宝石的魔力值最小花费。
数据范围
1 <= n <= 100000，1 <= m<= 100000,1≤a,b,c≤n
输入样例
3 1
1 1 10
1 2 3
输出样例
1 1 2
样例解释
第一个宝石花费1，第二个宝石花费1，第三个宝石可以由第一个第二个宝石合成花费2。
题目分析
注意题目中并没有提出n 和 m 的值的大小。即可能出现一种宝石不止一种合成方法。
一开始我联想到的是动态规划，感觉有那么一些的关系。但是写到一半发先状态转移方程我找不到，各阶段也不是固定的，才发现好像写不了（我动态规划确实没好好学哈哈哈哈，之后再写）
代码
这个是我写的代码 应该是能通过的。嘿嘿嘿我也没试过
n, m = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
a.insert(0, 0) # 在开头添加一个数 方便调用
a = [(i, j) for i, j in enumerate(a)] # ai = (序号，花费的法力)
comb = dict() # 用字典存放合成表
for i in range(n):
comb[a[i + 1][0]] = []
for i in range(m):
temp = list(map(int, input().split(' ')))
comb[temp[2]].append(temp[:2])
min_a = [-1 for i in range(n + 1)] # 表示第i个i的最小花费 -1 表示没找到最小值 一开始都没有最小值
# 无合成表 最小花费为本身 有合成表 看合成表中的最小值是否已知，已知则可计算。 min_i= min(ai, min_j +min_K)
p = [i for i in range(1, n + 1)] # 调查队列
while p:
x = p.pop(0)
if not comb[x]: # 没有合成表 最小值则为直接合成的法力值
min_a[x] = a[x][1]
else: # 有合成表 找最小的
flag = 0 # 0 表示合成表中的最小值都已知
for i in range(len(comb[x])): # x 有几种合成方式
for j in range(2):
if min_a[comb[x][i][j]] == -1: # 有一个值没找到最值
flag = 1
if flag == 1:
p.append(x)
else: # 都有最值
ans = [a[x][1]]
for i in range(len(comb[x])):
ans.append(min_a[comb[x][i][0]] + min_a[comb[x][i][1]])
min_a[x] = min(ans)
ans = [f'{i}' for i in min_a[1:]]
print(" ".join(ans))
ac代码
n, m = map(int, input().split(' '))
magic = list(map(int, input().split(' ')))
magic.insert(0, -1)
path = []
for _ in range(0, m):
path.append(list(map(int, input().split(' '))))
flag = True
while flag:
flag = False
for i in range(m):
a, b, c = path[i]
if magic[a] + magic[b] < magic[c]: # 如果有一个的值能变的更小则继续遍历 当所有的值都不能压缩时则全都到了最小值还是比较好想的
magic[c] = magic[a] + magic[b]
flag = True
print(str(magic[1:]).replace(',', '')[1:-1]) # 最后的[1：-1]是为了去掉 “中括号‘
备注
若有错误，欢迎各位一起探讨。
