题意

题目链接

Sol

做的时候忘记写题解了

可以参考这位大爷

#include<bits/stdc++.h>

#define Pair pair<int, int>

#define MP make_pair

#define fi first

#define se second

using namespace std;

const int MAXN = 2e6 + 10;

inline int read() {

    char c = getchar(); int x = 0, f = 1;

    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}

    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

    return x * f;

}

int N, S, M, Q, c[MAXN], vis[MAXN], ga[MAXN], ans[MAXN], fa[MAXN], dis[MAXN];

vector<Pair> v[MAXN];

struct Edge {

    int u, v, w;

    bool operator < (const Edge &rhs) const {

        return w < rhs.w;

    }

}E[MAXN];

struct Query {

    int x, y, b, id;

    bool operator < (const Query &rhs) const {

        return b < rhs.b;

    }

}q[MAXN];

void Dij() {

    memset(dis, 0x3f, sizeof(dis));

    priority_queue<Pair> q;

    for(int i = 1; i <= S; i++) ga[c[i]] = c[i], dis[c[i]] = 0, q.push(MP(0, c[i]));

    while(!q.empty()) {

        if(vis[q.top().se]) {q.pop(); continue;}

        int p = q.top().se; q.pop(); vis[p] = 1;

        for(int i = 0; i < v[p].size(); i++) {

            int to = v[p][i].fi, w = v[p][i].se;

            if(dis[to] > dis[p] + w)

                dis[to] = dis[p] + w, q.push(MP(-dis[to], to)), ga[to] = ga[p];

        }

    }

}

int find(int x) {

    return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);

}

void unionn(int x, int y) {

    fa[find(x)] = find(y);

}

void Build() {

    for(int i = 1; i <= N; i++) fa[i] = i;

    int tmp = 0;

    for(int i = 1; i <= M; i++) {

        int x = E[i].u, y = E[i].v;

        if(ga[x] == ga[y]) continue;

        E[++tmp] = (Edge) {ga[x], ga[y], dis[x] + dis[y] + E[i].w};

    }

    sort(E + 1, E + tmp + 1);

    sort(q + 1, q + Q + 1);

    int cur = 1;

    for(int i = 1; i <= Q; i++) {

        while(cur <= tmp && E[cur].w <= q[i].b) unionn(E[cur].u, E[cur].v), cur++;

        ans[q[i].id] = (bool)(find(q[i].x) == find(q[i].y));

    }

}

int main() {

    N = read(); S = read(); M = read();

    for(int i = 1; i <= S; i++) c[i] = read();

    for(int i = 1; i <= M; i++) {

        int x = read(), y = read(), z = read();

        E[i] = (Edge) {x, y, z};

        v[x].push_back(MP(y, z));

        v[y].push_back(MP(x, z));

    }

    Dij();

    Q = read();

    for(int i = 1; i <= Q; i++) q[i].x = read(), q[i].y = read(), q[i].b = read(), q[i].id = i;

    Build();

    for(int i = 1; i <= Q; i++) puts(ans[i] ? "TAK" : "NIE");

    return 0;

}

/*

6 4 5

1 5 2 6

1 3 1

2 3 2

3 4 3

4 5 5

6 4 5

4

1 2 4

2 6 9

1 5 9

6 5 8

*/