bzoj4144
2024-08-27 07:48:33
最短路+最小生成树
有点忘了...
这题只要判断能不能就行了
具体做法是把所有加油站放到堆里然后跑dij,然后把边权w=d[u]+d[v]+w,跑最小生成树
对于点对(x,y)是否能到达只要判断最大瓶颈路的长度是否>b就行了
具体原因是因为对于一条边(u,v),边权表示了经过这条边的最小油量。
然后最小生成树一边跑,一边离线就行了
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + ;
namespace IO
{
const int Maxlen = N * ;
char buf[Maxlen], *C = buf;
int Len;
inline void read_in()
{
Len = fread(C, , Maxlen, stdin);
buf[Len] = '\0';
}
inline void fread(int &x)
{
x = ;
int f = ;
while (*C < '' || '' < *C) { if(*C == '-') f = -; ++C; }
while ('' <= *C && *C <= '') x = (x << ) + (x << ) + *C - '', ++C;
x *= f;
}
inline void fread(long long &x)
{
x = ;
long long f = ;
while (*C < '' || '' < *C) { if(*C == '-') f = -; ++C; }
while ('' <= *C && *C <= '') x = (x << ) + (x << ) + *C - '', ++C;
x *= f;
}
inline void read(int &x)
{
x = ;
int f = ; char c = getchar();
while(c < '' || c > '') { if(c == '-') f = -; c = getchar(); }
while(c >= '' && c <= '') { x = (x << ) + (x << ) + c - ''; c = getchar(); }
x *= f;
}
inline void read(long long &x)
{
x = ;
long long f = ; char c = getchar();
while(c < '' || c > '') { if(c == '-') f = -; c = getchar(); }
while(c >= '' && c <= '') { x = (x << 1ll) + (x << 3ll) + c - ''; c = getchar(); }
x *= f;
}
} using namespace IO;
int rd()
{
int x = , f = ; char c = getchar();
while(c < '' || c > '') { if(c == '-') f = -; c = getchar(); }
while(c >= '' && c <= '') { x = x * + c - ''; c = getchar(); }
return x * f;
}
int n, m, Q, cnt = , s;
int head[N], ans[N], c[N], fa[N], d[N], rank[N];
struct edge {
int nxt, to, w;
} e[N << ];
struct Edge {
int u, v, w;
Edge() {}
Edge(int u, int v, int w) : u(u), v(v), w(w) {}
bool friend operator < (const Edge &a, const Edge &b) {
return a.w < b.w;
}
} E[N];
struct Query {
int u, v, id, b;
bool friend operator < (const Query &a, const Query &b) {
return a.b < b.b;
}
} que[N];
void link(int u, int v, int w)
{
e[++cnt].nxt = head[u];
head[u] = cnt;
e[cnt].to = v;
e[cnt].w = w;
}
int find(int x)
{
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
int main()
{
read_in();
fread(n);
fread(s);
fread(m);
memset(d, 0x7f7f, sizeof(d));
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
for(int i = ; i <= s; ++i)
{
fread(c[i]);
d[c[i]] = ;
q.push(make_pair(, c[i]));
}
for(int i = ; i <= m; ++i)
{
int u, v, w;
fread(u);
fread(v);
fread(w);
E[i] = Edge(u, v, w);
link(u, v, w);
link(v, u, w);
}
fread(Q);
for(int i = ; i <= Q; ++i)
{
fread(que[i].u);
fread(que[i].v);
fread(que[i].b);
que[i].id = i;
}
sort(que + , que + Q + );
while(!q.empty())
{
pair<int, int> o = q.top();
q.pop();
int u = o.second;
if(o.first > d[u]) continue;
for(int i = head[u]; i; i = e[i].nxt) if(d[e[i].to] > d[u] + e[i].w)
{
d[e[i].to] = d[u] + e[i].w;
q.push(make_pair(d[e[i].to], e[i].to));
}
}
for(int i = ; i <= m; ++i) E[i].w += d[E[i].u] + d[E[i].v];
sort(E + , E + m + );
for(int i = ; i <= n; ++i) fa[i] = i;
for(int i = , j = ; i <= Q; ++i)
{
while(j + <= m && E[j + ].w <= que[i].b)
{
++j;
int u = find(E[j].u), v = find(E[j].v);
if(u == v) continue;
if(rank[u] < rank[v]) swap(u, v);
rank[u] += rank[v];
fa[u] = v;
}
ans[que[i].id] = find(que[i].u) == find(que[i].v);
}
for(int i = ; i <= Q; ++i) puts(ans[i] ? "TAK" : "NIE");
return ;
}
最新文章
- IOS热更新-JSPatch实现原理+Patch现场恢复
- wamp链接mysql数据库
- 8 Regular Expressions You Should Know
- linux C语言getopt()函数的使用
- Linux常用命令及vim的使用、vim常用插件(推荐)
- 在TreeWidget中增加右键菜单功能 以及TreeWidget的基本用法
- php使用curl设置超时的重要性
- 快乐Node码农的十个习惯 转
- c++中vector的pair与make_pair的使用,双关键字排序
- shell中条件判断语法与判断条件小结
- sql 选取分组中的第一条,显示聚合以外的列,having字句的使用
- PHPExcel 读取 xls
- java初级笔记
- lua入门demo(HelloWorld+redis读取)
- WORLD 文件格式的保存
- flask 初学1
- 二叉搜索树与双向链表(python)
- ubuntu下 net core 安装web模板
- 使用";+";进行字符串拼接
- LINUX下IDEA等工具调试项目时提示:Unable to open debugger port