即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

魔法宝石

编程语言 xinxiaxindong 10℃ 0评论
本文目录
[隐藏]

1.Description

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

2.Input

第一行为数据组数T(1≤T≤3)。


对于每组数据,首先一行为n,m(1≤n,m≤10^5)。分别表示魔法宝石种类数和合成魔法的数量。


之后一行n个数表示a1到an。(1≤ai≤10^9)。a_i表示合成第i种宝石所需的魔力值。


之后m行,每行三个数a,b,c(1≤a,b,c≤n),表示一个第a种宝石和第b种宝石,可以合成一个第c种宝石。

3.Output

每组数据输出一行n个数,其中第i个数表示合成第i种宝石的魔力值最小花费。

4.Sample Input

1


3 1


1 1 10


1 2 3

5.Sample Output

1 1 2

5.1.Hint

5.2.题意

5.3.题解:

5.4.AC代码

#include 
#define ll long long
#define N 100005
struct node{
    int a1,a2,an;
}num[N];
int cst[N];
int main(){
    int t;
    scanf("%d",&t);
    int n,m;
    while (t--){
        scanf("%d%d",&n,&m);
        for (int i = 1; i <= n; ++i){
            scanf("%d",&cst[i]);
        }
        for (int i = 1; i <= m; ++i){
            scanf("%d%d%d",&num[i].a1,&num[i].a2,&num[i].an);
        }
        int tk = 1;
        //我感觉这样写是会TLE的 最大时间复杂度o(m*mwhile (tk == 1){
            tk = 0;
            for (int i = 1; i <= m; ++i){
                if  (cst[num[i].an] > cst[num[i].a1]+cst[num[i].a2]){
                    cst[num[i].an] = cst[num[i].a1]+cst[num[i].a2];
                    tk = 1;
                }
            }
        }
        for (int i  = 1; i <= n; ++i){
            printf("%d%c",cst[i],i == n?'\n':' ');
        }
    }
    return 0;
}

转载请注明:CodingBlog » 魔法宝石

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情