首先可以很显然的知道题目中只与加油站有关，也就是说其他的点都是无用的，所以先考虑如何取代其他无用的点，如下图：
黑色代表加油站，红色代表无用的点，现在要去掉红色4号，那么考虑对于1,2,3节点新的边应该是什么样子。
考虑从3号节点到达1号，如果直接沿简单路径走，油量最小为7，而如果从3到2再到1，就只需要5就可以了，原因：
b<c&&b<a 所以a+b<a+c && b+c<a+c
顾这样的走法是最优的，这样一来我们就能得到一个性质，从当前节点到距离他最近的加油站再去往其他加油站不会更差。所以做多源最短路，记录每一个点最近的加油站，然后如果一条边链接的两个点的最近的加油站不同，就新建一条连接着两个加油站的边，权值显然
最后只需要做一次最小生成树判联性就好了。
#include<cstdio> #include<cstring> #include<iostream> #include<queue> #include<algorithm> #define maxn 200021 #define inf 0x3fffffff using namespace std; typedef pair<int,int>pii; int n,m,s,C[maxn],ans[maxn],Q,head[maxn],cnt; int dis[maxn],tot=1,f[maxn],vis[maxn],near[maxn]; struct que{ int x,y,d,id; bool operator<(const que& b)const{return d<b.d;} }qu[maxn]; struct data{ int a,b,c; bool operator<(const data& y)const{return c<y.c;} }nod[maxn*4]; struct edge{int v,next,w;}e[maxn*4]; void adde(int a,int b,int c){e[tot].v=b,e[tot].next=head[a],e[tot].w=c;head[a]=tot++;} int find(int x){return f[x]==x ? x : f[x]=find(f[x]);} void dijkstra(){ priority_queue<pii,vector<pii>,greater<pii> >q; for(int i=1;i<=n;i++)dis[i]=inf; for(int i=1;i<=s;i++){ dis[C[i]]=0;near[C[i]]=C[i];q.push(make_pair(0,C[i])); } while(!q.empty()){ int u=q.top().second;q.pop(); if(vis[u])continue;vis[u]=1; for(int v,i=head[u];i;i=e[i].next){ if(dis[v=e[i].v]>dis[u]+e[i].w){ dis[v]=dis[u]+e[i].w;near[v]=near[u]; q.push(make_pair(dis[v],v)); } } } } void build(){ for(int i=1;i<=n;i++){ for(int v,j=head[i];j;j=e[j].next){ if(near[i]!=near[v=e[j].v]){ nod[++cnt]=(data){near[i],near[v],dis[i]+dis[v]+e[j].w}; } } }sort(nod+1,nod+1+cnt); } void solve(){ int now=1; for(int i=1;i<=n;i++)f[i]=i; for(int i=1;i<=Q;i++){ while(now<=cnt&&nod[now].c<=qu[i].d){ int dx=find(nod[now].a),dy=find(nod[now].b); if(dx!=dy)f[dx]=dy; now++; } int dx=find(qu[i].x),dy=find(qu[i].y); if(dx==dy)ans[qu[i].id]=1; else ans[qu[i].id]=0; } for(int i=1;i<=Q;i++)if(ans[i])puts("TAK"); else puts("NIE"); } int main(){ scanf("%d%d%d",&n,&s,&m); for(int i=1;i<=s;i++)scanf("%d",C+i); for(int a,b,c,i=1;i<=m;i++){ scanf("%d%d%d",&a,&b,&c); adde(a,b,c);adde(b,a,c); }dijkstra(); build(); scanf("%d",&Q); for(int i=1;i<=Q;i++)scanf("%d%d%d",&qu[i].x,&qu[i].y,&qu[i].d),qu[i].id=i; sort(qu+1,qu+1+Q); solve(); return 0; }