题目描述
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 = Truewhile 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 = Trueprint(str(magic[1:]).replace(',', '')[1:-1]) # 最后的[1：-1]是为了去掉 “中括号‘
备注
若有错误，欢迎各位一起探讨。