题面

给定一个\(n\)个点、\(m\)条边的带权无向图，其中有\(s\)个点是加油站。

每辆车都有一个油量上限\(b\)，即每次行走距离不能超过\(b\)，但在加油站可以补满。

\(q\)次询问，每次给出\(x,y,b\)，表示出发点是\(x\)，终点是\(y\)，油量上限为\(b\)，且保证\(x\)点和\(y\)点都是加油站，请回答能否从\(x\)走到\(y\)。

• \(n,m,q\leq2*10^5\)

  解析

  其实如果这个图上只有加油站，那和\(noip2013\)货车运输是一道题。

  所以让我们把这个图简化成只有加油站的形式。

这要求我们求出图上加油站两两之间的距离。

然而不会饿。。。

（是同一个套路）

从每个加油站出发跑多源最短路（\(Dijstra\))。

如果一个点距离可以被更新，就更新，并标记离它最近的加油站。

否则，如果这个点被另一个加油站标记过，就说明这个点在当前加油站和标记加油站的最短路径上，可以利用距离信息，在新图上为这两个加油站建边。

这样就简化完了。

然后在新图上求出最小生成树，询问用倍增+\(ST\)表处理即可。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define ll long long#define re register#define il inline#define pi pair
           
            #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
            
             <<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
             
              
               ,greater
               
                 >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]) 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;}