最短路+最小生成树

有点忘了...

这题只要判断能不能就行了

具体做法是把所有加油站放到堆里然后跑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 ;
}

最新文章

  1. IOS热更新-JSPatch实现原理+Patch现场恢复
  2. wamp链接mysql数据库
  3. 8 Regular Expressions You Should Know
  4. linux C语言getopt()函数的使用
  5. Linux常用命令及vim的使用、vim常用插件(推荐)
  6. 在TreeWidget中增加右键菜单功能 以及TreeWidget的基本用法
  7. php使用curl设置超时的重要性
  8. 快乐Node码农的十个习惯 转
  9. c++中vector的pair与make_pair的使用,双关键字排序
  10. shell中条件判断语法与判断条件小结
  11. sql 选取分组中的第一条,显示聚合以外的列,having字句的使用
  12. PHPExcel 读取 xls
  13. java初级笔记
  14. lua入门demo(HelloWorld+redis读取)
  15. WORLD 文件格式的保存
  16. flask 初学1
  17. 二叉搜索树与双向链表(python)
  18. ubuntu下 net core 安装web模板
  19. 使用&quot;+&quot;进行字符串拼接
  20. LINUX下IDEA等工具调试项目时提示:Unable to open debugger port

热门文章

  1. Linux mm相关的问题
  2. HRBUST2030(dfs)
  3. PHP ORM操作MySQL数据库
  4. Android多线程下载大文件解析
  5. C#基础关键字
  6. 用户&#39;sa&#39;登录失败(错误18456)解决方案图解
  7. Android调用JNI本地方法经过有点改变
  8. MongoDB 征途
  9. iperf3 测试路由器吞吐率
  10. TXT文本写入数据库