没边权的可以跑$bfs$, 那有边权的就跑$dijk$吧

懵逼的 题目

BZOJ

被Refun老狗鳖抢了第321个AC的_(:зゝ∠)_

扯淡的题解

大胆联想$Dispwnl$给我推的一道题

那个题权都为$1$可以跑$bfs$, 这个题既然边劝不一样我们就直接$dijk$咯…

在这种[在一个图中找一些关键点的最小生成树]的问题…我们都可以把关键点直接放到队列里, 从这些关键点分别开始最短路 / $bfs$, 这样可以减少很多的边数…因为途中经过某个关键点进行中转的路径肯定不是最优的路径, 不可能放在最小生成树里…

沙茶的 代码

ta给的图不一定联通真是太真实了…

倍增的lgn没有赋值更是太真实了…

/**************************************************************
    Problem: 4144
    User: Cansult
    Language: C++
    Result: Accepted
    Time:7056 ms
    Memory:111496 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#define MAXN (200000 + 5)
#define MAXM (500000 + 5)
#define MAXL (40 + 5)
using namespace std;
struct edg {
    int from, to, next, cost;
} tb[MAXN << 1], eb[MAXM << 1], kb[MAXM];
struct node {
    int from, bh, cost;
    node() {}
    node(int fr, int b, int co): from(fr), bh(b), cost(co) {}
};
struct cmp1 {
    bool operator () (const node& x, const node& y) { return x.cost > y.cost; }
};
int tg[MAXN], cntt, eg[MAXN], cnte, cntk, n, m, s, c[MAXN], q, lgn, d[MAXN][MAXL], deep[MAXN], maxc[MAXN][MAXL], fa[MAXN], dis[MAXN], belong[MAXN];
void adn(edg* bx, int* gx, int& cntx, int from, int to, int cost) {
    bx[++cntx].next = gx[from];
    bx[cntx].from = from, bx[cntx].to = to, bx[cntx].cost = cost;
    gx[from] = cntx;
}
int find(int x) { return (fa[x] == x) ? x : (fa[x] = find(fa[x])); }
void uni(int x, int y) { fa[find(x)] = find(y); }
bool cmp(const edg x, const edg y) { return x.cost < y.cost; }
void init() {
    bool vis[MAXN];
    memset(vis, false, sizeof(vis));
    memset(dis, 0x7f, sizeof(dis));
    priority_queue<node, vector<node>, cmp1> q;
    for (int i = 1; i <= s; i++) q.push(node(c[i], c[i], dis[c[i]] = 0));
    while (!q.empty()) {
        node dq = q.top();
        q.pop();
        if (vis[dq.bh]) continue;
        vis[dq.bh] = true;
        belong[dq.bh] = dq.from;
        for (int i = eg[dq.bh]; i; i = eb[i].next)
            if (dis[eb[i].to] > dis[dq.bh] + eb[i].cost)
                q.push(node(dq.from, eb[i].to, dis[eb[i].to] = dis[dq.bh] + eb[i].cost));
    }
}
void kruskal() {
    sort(kb + 1, kb + m + 1, cmp);
    for (int i = 1; i <= n; i++) fa[i] = i;
    for (int i = 1; i <= m; i++)
        if (find(kb[i].from) != find(kb[i].to)) {
            uni(kb[i].from, kb[i].to);
            adn(tb, tg, cntt, kb[i].from, kb[i].to, kb[i].cost);
            adn(tb, tg, cntt, kb[i].to, kb[i].from, kb[i].cost);
//          printf("%d %d %d\n", kb[i].from, kb[i].to, kb[i].cost);
        }
}
void dfs(int dq) {
    deep[dq] = deep[d[dq][0]] + 1;
    for (int i = 1; i <= lgn; i++)   d[dq][i] = d[d[dq][i - 1]][i - 1], maxc[dq][i] = max(maxc[d[dq][i - 1]][i - 1], maxc[dq][i - 1]);
    for (int i = tg[dq]; i; i = tb[i].next)
        if (tb[i].to != d[dq][0])
            d[tb[i].to][0] = dq, maxc[tb[i].to][0] = tb[i].cost, dfs(tb[i].to);
}
int lca(int x, int y) {
    int re = 0;
    if (deep[x] < deep[y])   swap(x, y);
    for (int i = lgn; i >= 0; i--)
        if (deep[d[x][i]] >= deep[y])
            re = max(maxc[x][i], re), x = d[x][i];
    if (x == y)
        return re;
    for (int i = lgn; i >= 0; i--)
        if (d[x][i] != d[y][i])
            re = max(re, max(maxc[x][i], maxc[y][i])), x = d[x][i], y = d[y][i];
    return max(re, max(maxc[x][0], maxc[y][0]));
}
int lg(int x) {
    int re = 0;
    while ((1 << re) < x)  ++re;
    return re;
}
int main() {
    scanf("%d%d%d", &n, &s, &m);
    lgn = lg(n);
    for (int i = 1; i <= s; i++) scanf("%d", &c[i]);
    for (int i = 1, srx, sry, src; i <= m; i++)
        scanf("%d%d%d", &srx, &sry, &src), adn(eb, eg, cnte, srx, sry, src), adn(eb, eg, cnte, sry, srx, src);
    init(); 
/*  for (int i = 1; i <= n; i++)
        printf("%d ", belong[i]);
    puts(""); */
    for (int i = 1; i <= cnte; i += 2) {
        ++cntk;
        kb[cntk].from = belong[eb[i].from];
        kb[cntk].to = belong[eb[i].to];
        kb[cntk].cost = dis[eb[i].from] + dis[eb[i].to] + eb[i].cost;
    }
    kruskal();
    for (int i = 1; i <= s; i++)
        if (!d[c[i]][0])
            maxc[c[i]][0] = 0, d[c[i]][0] = 1, dfs(c[i]);
    int q;
    scanf("%d", &q);
    for (int i = 1, srx, sry, srb; i <= q; i++) {
        scanf("%d%d%d", &srx, &sry, &srb);
        if (find(belong[srx]) != find(belong[sry]) || lca(belong[srx], belong[sry]) > srb)
            puts("NIE");
        else
            puts("TAK");

    }
    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
 */

By 准备退役旅游的 Cansult