HAUT--1262--魔法宝石（暴力）

1262: 魔法宝石

时间限制: 2 秒内存限制: 64 MB
提交: 525 解决: 157
提交状态

题目描述

小s想要创造n种魔法宝石。小s可以用ai的魔力值创造一棵第i种魔法宝石，或是使用两个宝石合成另一种宝石（不消耗魔力值）。请你帮小s算出合成某种宝石的所需的最小花费。

输入

第一行为数据组数T（1≤T≤3）。
对于每组数据，首先一行为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 1 2

 1 /*
 2     Name: HAUT--1262--魔法宝石
 3     Copyright: ©2017 日天大帝
 4     Author: 日天大帝
 5     Date: 27/04/17 09:54
 6     Description: 暴力 ,注意下标要从1开始，因为宝石的魔力值不会为0  
 7 */
 8 
 9 #include<iostream>
10 #include<cstring>
11 #include<algorithm>
12 using namespace std;
13 const int MAX = 1e5+10;
14 int res[MAX];
15 struct magic{
16     int a,b,c;
17 }arr[MAX];
18 int main(){
19     int t;cin>>t;
20     while(t--){
21         memset(arr,0,sizeof(0));
22         memset(res,0,sizeof(0));
23         int n,m;cin>>n>>m;
24         for(int i=1; i<=n; ++i)cin>>res[i];
25         for(int i=1; i<=m; ++i)cin>>arr[i].a>>arr[i].b>>arr[i].c;
26         int o = 200;
27         while(o--){
28             for(int i=1; i<=m; ++i){
29                 res[arr[i].c] = min(res[arr[i].c], res[arr[i].b]+res[arr[i].a]);
30             }
31         }
32         for(int i=1; i<n; ++i)cout<<res[i]<<" ";
33         cout<<res[n]<<endl;
34     }
35     return 0;
36 }