davidwang's Blog

就是一结论题目

首先如果所有点都是加油站，那么把询问离线维护可达的生成森林就OK了

现在有些点不是加油站

我们预处理出每个不是加油站的点距离最近的加油站，就变成了一个蜘蛛网的结构(其实是一个树)

然后我们对于原来的每条边对应这两个加油站之间的边如果原来有一条(x,y,d)的边，记bel[x]表示距离x最近的加油站，d[x]表示距离x最近的加油站的距离，那么这样一条边对应着(bel[x],bel[y],d+d[x]+d[y])这样一个点，然后问题就解决了

证明：

我还是大体证明了以下这个结论（其实就一个拟阵）

//coder : davidwang
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <bitset>
#include <deque>
using namespace std;
#define LL long long
#define X first
#define Y second
template<typename T>
inline T sqr(const T &x){ return x*x; }
inline int read()
{
	int ret=0,f=1; char ch;
	for (ch=getchar();ch<'0' || ch>'9';ch=getchar())
		if (ch=='-') f=-f;
	for (;'0'<=ch && ch<='9';ch=getchar())
		ret=ret*10+ch-'0';
	return ret*f;
}
const int N = 200010;
const LL inf = 1LL<<60;
struct edge{
	int x,y,l,pos;
	edge(int x=0,int y=0,int l=0,int pos=0): x(x),y(y),l(l),pos(pos){}
	int operator<(const edge &A) const{
		return l<A.l || (l==A.l && pos<A.pos);
	}
}e[N*4];
vector<pair<int,int> >g[N];
vector<pair<int,int> >::iterator it;
int q[N+2],bel[N],ans[N],in[N];
LL d[N];
inline int next(int &x){ x=(x%N+1); return x;}
struct UnionFindSet{
	int Set[N],Size[N];
	inline void init(int n){
		for (int i=1;i<=n;i++){
			Set[i]=i;
			Size[i]=1;
		}
	}
	int find(int x){
		if (Set[x]==x) return x;
		Set[x]=find(Set[x]);
		return Set[x];
	}
	inline int join(int x,int y){
		x=find(x),y=find(y);
		if (x==y) return 0;
		if (Size[x]>Size[y]) swap(x,y);
		Set[x]=y; Size[y]+=Size[x];
		return 1;
	}
}s;
int n,m,T,cnt,E;
int main()
{
#ifndef ONLINE_JUDGE
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
#endif
	n=read(); m=read(); E=read();
	for (int i=1;i<=n;i++) d[i]=inf;
	for (int i=1;i<=m;i++){
		int x=read();
		bel[x]=x;
		d[x]=0;
		in[x]=1;
		q[i]=x;
	}
	for (int i=1;i<=E;i++){
		int x=read(),y=read(),z=read();
		g[x].push_back(make_pair(y,z));
		g[y].push_back(make_pair(x,z));
	}
	int head=0,tail=m;
	while (head!=tail){
		int u=q[next(head)];
		for (it=g[u].begin();it!=g[u].end();it++){
			if (d[it->X]>d[u]+it->Y){
				d[it->X]=d[u]+it->Y;
				bel[it->X]=bel[u];
				if (!in[it->X]){
					q[next(tail)]=it->X;
					in[it->X]=1;
				}
			}
		}
		in[u]=0;
	}
	for (int i=1;i<=n;i++)
		for (it=g[i].begin();it!=g[i].end();it++)
			if (bel[it->X] != bel[i]){
				LL now=d[i]+d[it->X]+it->Y;
				if (now>2e9) continue;
				e[++cnt]=edge(bel[i],bel[it->X],(int)now);
			}
	T=read();
	for (int i=1;i<=T;i++){
		cnt++;
		e[cnt].x=read(); e[cnt].y=read();
		e[cnt].l=read();
		e[cnt].pos=i;
	}
	sort(e+1,e+cnt+1);
	s.init(n);
	for (int i=1;i<=cnt;i++){
		if (e[i].pos==0)
			s.join(e[i].x,e[i].y);
		else
			ans[e[i].pos]=s.find(e[i].x)==s.find(e[i].y);
	}
	for (int i=1;i<=T;i++) printf("%s\n",ans[i]?"TAK":"NIE");
	return 0;
}