魔法宝石

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 302    Accepted Submission(s): 102

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


不断地扫，直到没有新的宝石合成。

不断维护得到宝石所需要的能量，（因为合成宝石不需要能量）


#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 100005 
using namespace std;

int main(){
	int t;
	cin>>t;
	int a[maxn];
	while(t--){
		int n,m;
		int a1[maxn],b1[maxn],c1[maxn];
		scanf("%d%d",&n,&m);
		for(int i=0;i<=n;i++){
			a[i]=a1[i]=b1[i]=c1[i]=0;
		}
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
		}
		for(int i=0;i<m;i++){
			scanf("%d%d%d",&a1[i],&b1[i],&c1[i]);
		}
		for(int i=0;i<999999;i++){
			bool ifchange=1;
			for(int j=0;j<m;j++){
				if(a[a1[j]]+a[b1[j]]<a[c1[j]]){
					ifchange = 0;
					a[c1[j]]=a[a1[j]]+a[b1[j]];
				}
			}
			if(ifchange)break;	
		}
		for(int i=1;i<=n-1;i++){
			printf("%d ",a[i]);
		} 
		printf("%d\n",a[n]);
	}
	return 0;
}