魔法宝石（类似dp 杭电排位赛-2）
魔法宝石
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种宝石。
对于每组数据，首先一行为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;
}
三环集团开奖41人在聊