题意

Sol

做的时候忘记写题解了

可以参考

#include
    
     #define Pair pair
     
      #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
      
        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
       
         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 51 5 2 61 3 12 3 23 4 34 5 56 4 541 2 42 6 91 5 96 5 8*/