题意：

给一个n个点m条边的带权无向图，其中k个点是加油站，每个加油站可以加满油，但不能超过车的油量上限。有q个询问，每次给出x,y,b，保证x,y都是加油站，问一辆油量上限为b的车从x出发能否到达y？

$n,m,s,q\leq 2\times 10^5.$

 

题解：

只有加油站是有用的点，问题可以转化为求一个加油站的排列，使得相邻两个加油站距离最大值小于等于油量上限。一个简单粗暴的想法是求出加油站两两最短路，然后直接上MST，离线处理询问。

其实上述的暴力做法是有很多冗余的（有很多边用不到）。考虑更优的建边方式。可以发现一个加油站每次往离他最近的加油站走最优（显然，不然为什么求的是MST）。我们将所有加油站扔进dijkstra里跑多源最短路，求出距离每个点最近的加油站，记为nearest[]。对于原图上一条边$u\sim v$，假如nearest[u]=nearest[v]，那么这条边没有用；否则，建一条$nearest[u]\sim nearest[v]$的边，边权为dis(u,nearest[u])+dis(v,nearest[v])+dis(u,v)。相当于添加了一条nearest[u]到nearest[v]的路径（经过u-v这条边）。那么将所有原图的边遍历完之后，也恰好加入了所有可能在MST上的加油站之间的边。

那么再对这个新图跑MST，离线处理询问即可。复杂度$\mathcal{O}(n\log n+\alpha(m+q))$。

 

code:

1 #include
      
        2 #define rep(i,x,y) for (int i=(x);i<=(y);i++) 3 #define ll long long 4 #define inf 1000000001 5 #define y1 y1___ 6 #define pli pair
       
         7 #define fi first 8 #define se second 9 using namespace std;10 char gc(){11     static char buf[100000],*p1=buf,*p2=buf;12     return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;13 }14 #define gc getchar15 ll read(){16     char ch=gc();ll x=0;int op=1;17     for (;!isdigit(ch);ch=gc()) if (ch=='-') op=-1;18     for (;isdigit(ch);ch=gc()) x=(x<<1)+(x<<3)+ch-'0';19     return x*op;20 }21 #define N 20000522 int n,k,m,x,cnt,head[N],nrst[N],fa[N];ll dis[N];bool vis[N];23 struct edge{
    int to,nxt,w;}e[N<<1];24 struct ask{
    int x,y,w,id;}q[N];25 struct node{26     int x,y;ll w;node(){}27     node(int x_,int y_,ll w_){x=x_,y=y_,w=w_;}28 }a[N];29 bool cmp_q(ask x,ask y){
    return x.w
        
         ,greater
         
           > q_;32 void adde(int x,int y,int z){33     e[++cnt].to=y;e[cnt].nxt=head[x];head[x]=cnt;34     e[cnt].w=z;35 }36 void dij(){37     while (!q_.empty()){38         int u=q_.top().se;q_.pop();39         if (vis[u]) continue;vis[u]=1;40         for (int i=head[u];i;i=e[i].nxt){41             int v=e[i].to;42             if (dis[v]>dis[u]+e[i].w)43                 dis[v]=dis[u]+e[i].w,q_.push(pli(dis[v],v)),nrst[v]=nrst[u];44         }45     }46 }47 void build(){48     cnt=0;49     rep (u,1,n) for (int i=head[u];i;i=e[i].nxt){50         int v=e[i].to;51         if (nrst[u]!=nrst[v]&&nrst[u]