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 */
下一篇: 还变形金刚呢