C、 Tachibana Kanade Loves Review

最小生成树裸题，考虑多加入一个虚拟节点，这个点到其他点的距离就是学会那个题所花费的时间。

https://ac.nowcoder.com/acm/contest/548/C

Code:

#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct node
{
    int in;
    int to;
    int w;
}edge[6000005];
int que[1000005], tt[1000005], cnt;
namespace IO {
    char buf[1 << 15], *S, *T;
    inline char gc() {
        if (S == T) {
            T = (S = buf) + fread(buf, 1, 1 << 15, stdin);
            if (S == T)return EOF;
        }
        return *S++;
    }
    inline int read() {
        int x; bool f; char c;
        for (f = 0; (c = gc()) < '0' || c > '9'; f = c == '-');
        for (x = c ^ '0'; (c = gc()) >= '0' && c <= '9'; x = (x << 3) + (x << 1) + (c ^ '0'));
        return f ? -x : x;
    }
    inline long long readll() {
        long long x; bool f; char c;
        for (f = 0; (c = gc()) < '0' || c > '9'; f = c == '-');
        for (x = c ^ '0'; (c = gc()) >= '0' && c <= '9'; x = (x << 3) + (x << 1) + (c ^ '0'));
        return f ? -x : x;
    }
}
using IO::read;
using IO::readll;
int getf(int k)
{
    return que[k] == k ? k : que[k] = getf(que[k]);
}
void add(int a, int b, int c)
{
    edge[cnt++] = node{ a,b,c };
}
int main()
{
    int n, m, k, a, b, c;
    ll t;
    n = read(); m = read(); k = read(); t = readll();
    for (int i = 1; i <= n + 1; i++)
        que[i] = i;
    for (int i = 1; i <= n; i++)
        tt[i] = read();
    while (k--)
    {
        a = read();
        tt[a] = 0;
    }
    for (int i = 1; i <= n; i++)
        add(i, n + 1, tt[i]);
    while (m--)
    {
        a = read();
        b = read();
        c = read();
        add(a, b, c);
    }
    sort(edge, edge + cnt, [](node q, node w) {
        return q.w < w.w;
    });
    ll ans = 0;
    for (int i = 0; i < cnt; i++)
    {
        int q = getf(edge[i].in), w = getf(edge[i].to);
        if (q != w)
        {
            que[q] = w;
            ans += edge[i].w;
        }
    }
    puts(ans <= t ? "Yes" : "No");
}