Problem Description
小s想要创造n种魔法宝石。小s可以用 ai的魔力值创造一棵第i种魔法宝石,或是使用两个宝石合成另一种宝石(不消耗魔力值)。请你帮小s算出合成某种宝石的所需的最小花费。
Input
第一行为数据组数T(1≤T≤3)。 对于每组数据,首先一行为n,m(1≤n,m≤10^5)。分别表示魔法宝石种类数和合成魔法的数量。 之后一行n个数表示 a1到an。(1≤ai≤10^9)。ai表示合成第i种宝石所需的魔力值。之后m行,每行三个数a,b,c(1≤a,b,c≤n),表示一个第a种宝石和第b种宝石,可以合成一个第c种宝石。
Output
每组数据输出一行n个数,其中第i个数表示合成第i种宝石的魔力值最小花费。
Sample Input
1 3 1 1 1 10 1 2 3
Sample Output
1 1 2
1、使用结构体去保存宝石变化的情况
2、while(1)一直循环找到每个宝石的最小费用后跳出
#includeusing namespace std;struct node{int x,y,z;}b[100000+5]; int main(){ int a[100000+5]; int i,j; int t; cin>>t; bool cnt; while(t--) { int n,m; cin>>n>>m; for(i=1;i<=n;i++) cin>>a[i]; for(i=1;i<=m;i++) cin>>b[i].x>>b[i].y>>b[i].z; while(1) { cnt=false; for(i=1;i<=m;i++){ if(a[b[i].x]+a[b[i].y]