[AMPPZ2014]Petrol

最小生成树 倍增 图论 ST表

题面

给定一个$n$个点、$m$条边的带权无向图，其中有$s$个点是加油站。
每辆车都有一个油量上限$b$，即每次行走距离不能超过$b$，但在加油站可以补满。
$q$次询问，每次给出$x,y,b$，表示出发点是$x$，终点是$y$，油量上限为$b$，且保证$x$点和$y$点都是加油站，请回答能否从$x$走到$y$。

• $n,m,q\leq2*10^5$

解析

其实如果这个图上只有加油站，那和$noip2013$货车运输是一道题。
所以让我们把这个图简化成只有加油站的形式。

这要求我们求出图上加油站两两之间的距离。
然而不会饿。。。

（[bzoj4242]水壶是同一个套路）
从每个加油站出发跑多源最短路（$Dijstra$)。
如果一个点距离可以被更新，就更新，并标记离它最近的加油站。
否则，如果这个点被另一个加油站标记过，就说明这个点在当前加油站和标记加油站的最短路径上，可以利用距离信息，在新图上为这两个加油站建边。

这样就简化完了。
然后在新图上求出最小生成树，询问用倍增+$ST$表处理即可。

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#define ll long long
#define re register
#define il inline
#define pi pair<int,int>
#define mk make_pair
#define fp(i,a,b) for(re int i=a;i<=b;++i)
#define fq(i,a,b) for(re int i=a;i>=b;--i)
using namespace std;
const int N=2e5+100;
int n,m,h[N],cnt,dis[N],oil[N],tot,f[N],d[N],fa[18][N],st[18][N],q,top;
bool vis[N];
struct Edge{int to,nxt,w;}e[N<<1];
struct dat{int u,v,w;il bool operator < (const dat &o) const {return w<o.w;}}a[N<<1];
il void add(re int u,re int v,re int w){e[++cnt]=(Edge){v,h[u],w};h[u]=cnt;}
priority_queue<pi,vector<pi>,greater<pi> >Q;
il int find(re int x){return x==f[x]?x:f[x]=find(f[x]);}
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il int max(re int x,re int y){return x>y?x:y;}
il void dfs(re int u,re int ff)
{
  d[u]=d[ff]+1;
  fp(i,1,17)
    fa[i][u]=fa[i-1][fa[i-1][u]],st[i][u]=max(st[i-1][u],st[i-1][fa[i-1][u]]);
  for(re int i=h[u];i+1;i=e[i].nxt)
    {
      re int v=e[i].to;
      if(v==ff) continue;
      fa[0][v]=u;st[0][v]=e[i].w;
      dfs(v,u);
    }
}
il int solve(re int u,re int v)
{
  re int mx=0;
  if(d[u]<d[v]) swap(u,v);
  fq(i,17,0) if(d[fa[i][u]]>=d[v]) mx=max(mx,st[i][u]),u=fa[i][u];
  if(u==v) return mx;
  fq(i,17,0)
    if(fa[i][u]^fa[i][v])
      {
    mx=max(mx,st[i][u]);mx=max(mx,st[i][v]);
    u=fa[i][u];v=fa[i][v];
      }
  mx=max(mx,st[0][u]);mx=max(mx,st[0][v]);
  return mx;
}
int main()
{
  memset(h,-1,sizeof(h));memset(dis,63,sizeof(dis));
  n=gi();top=gi();m=gi();
  fp(i,1,top)
    {
      re int x=gi();
      oil[x]=x,dis[x]=0,Q.push(mk(0,x));
    }
  fp(i,1,m)
    {
      re int u=gi(),v=gi(),w=gi();
      add(u,v,w);add(v,u,w);
    }
  while(!Q.empty())
    {
      re int u=Q.top().second;Q.pop();
      if(vis[u]) continue;vis[u]=1;
      for(re int i=h[u];i+1;i=e[i].nxt)
    {
      re int v=e[i].to;
      if(dis[v]>dis[u]+e[i].w) dis[v]=dis[u]+e[i].w,oil[v]=oil[u],Q.push(mk(dis[v],v));
      else if(oil[v]^oil[u]) a[++tot]=(dat){oil[u],oil[v],dis[u]+dis[v]+e[i].w};
    }
    }
  sort(a+1,a+1+tot);
  memset(h,-1,sizeof(h));cnt=0;
  fp(i,1,n) f[i]=i;
  fp(i,1,tot)
    {
      re int u=a[i].u,v=a[i].v,w=a[i].w,fu=find(u),fv=find(v);
      if(fu^fv)
    {
          add(u,v,w);add(v,u,w);
      f[fv]=fu;
    }
    }
  fp(i,1,n) if(oil[i]==i&&!d[i]) dfs(i,0);
  q=gi();
  while(q--)
    {
      re int u=gi(),v=gi(),lim=gi();
      if(find(u)^find(v)) puts("NIE");
      else puts((solve(u,v)<=lim?"TAK":"NIE"));
    }
  return 0;
}