HAUT校赛魔法宝石暴力

た入场券 2022-01-10 04:37 168阅读 0赞

## 问题 C: 魔法宝石 ##

时间限制: 2 秒 内存限制: 64 MB  
提交: 505 解决: 149  
[提交][Link 1] [状态][Link 2]

#### 题目描述 ####

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

#### 输入 ####

第一行为数据组数*T*（1≤*T*≤3）。  
对于每组数据，首先一行为*n*,*m*(1≤*n*,*m*≤10^5)。分别表示魔法宝石种类数和合成魔法的数量。  
之后一行n个数表示*a*1到*an*。(1≤*ai*≤10^9)。a\_i表示合成第i种宝石所需的魔力值。  
之后n行，每行三个数*a*,*b*,*c*(1≤*a*,*b*,*c*≤*n*),表示一个第a种宝石和第b种宝石，可以合成一个第c种宝石。

#### 输出 ####

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

#### 样例输入 ####

13 11 1 101 2 3

#### 样例输出 ####

1 1 2

显然，每次更新最值小值就可以了，我把数据开到了1e2，这个应该满足上界了。

#include <map>
    #include <set>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <queue>
    #include <iostream>
    #include <stack>
    #include <cmath>
    #include <string>
    #include <vector>
    #include <cstdlib>
    //#include <bits/stdc++.h>
    //#define LOACL
    #define space " "
    #define lson o<<1, l, mid
    #define rson o<<1|1, mid+1, r
    #define ll o<<1
    #define rr o<<1|1
    using namespace std;
    typedef long long LL;
    //typedef __int64 Int;
    typedef pair<int, int> PAI;
    const int INF = 0x3f3f3f3f;
    const double ESP = 1e-5;
    const double PI = acos(-1.0);
    const int MOD = 1e9 + 7;
    const int MAXN = 1e5 + 10;
    const int MAX = 3000;
    int ar[MAXN];
    struct node 
    {
        int a, b, c;
    }data[MAXN];
    int main(int argc, char const *argv[])
    {
        int T, N, M;
        scanf("%d", &T);
        while (T--) {
            scanf("%d%d", &N, &M);
            for (int i = 1; i <= N; i++) scanf("%d", &ar[i]);
            for (int i = 0; i < M; i++) {
                int a, b, c;
                scanf("%d%d%d", &a, &b, &c);
                data[i].a = a;
                data[i].b = b;
                data[i].c = c;
                ar[c] = min(ar[c], ar[a] + ar[b]);
            }
            for (int i = 0; i < 1e2; i++) {
                for (int j = 0; j < M; j++) {
                    int ta = data[j].a;
                    int tb = data[j].b;
                    int tc = data[j].c;
                    ar[tc] = min(ar[tc], ar[ta] + ar[tb]);
                }
            }
            printf("%d", ar[1]);
            for (int i = 2; i <= N; i++) {
                printf(" %d", ar[i]);
            }
            printf("\n");
        }
        return 0;
    }

转载于:https://www.cnblogs.com/cniwoq/p/6770740.html

[Link 1]: http://218.28.220.249:50015/JudgeOnline/submitpage.php?cid=1020&pid=2&langmask=0
[Link 2]: http://218.28.220.249:50015/JudgeOnline/problemstatus.php?id=1262