欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

BZOJ4144: [AMPPZ2014]Petrol(最短路 最小生成树)

程序员文章站 2022-03-17 13:57:51
题意 "题目链接" Sol 做的时候忘记写题解了 可以参考 "这位大爷" cpp include define Pair pair define MP make_pair define fi first define se second using namespace std; const int ......

题意

题目链接

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

*/