AtCoder ABC #250 : Ex - Trespassing Takahashi

別解賢いな。
https://atcoder.jp/contests/abc250/tasks/abc250_h

問題

N頂点からなる連結無向グラフが与えられる。
各辺には長さが設定されている。
N点中K点には家が置かれている。

以下のクエリに答えよ。
家のある点Xから、家のある点Yに、辺に沿って移動できるか判定したい。
ただしその際、ある家から他の家まで、移動距離がT以下でなければならない。

解法

家だけの点同士における最小全域木を求める。
あとはクエリをT昇順でソートしておけば、距離T以下の辺を用いてXとYが同一連結成分に属するか判定できる。

問題は最小全域木の求め方。
想定解はブルーフカ法だが、別解の方がわかりやすい。
辺について、両端の頂点をu,v、辺の長さをcとする。
D[v]を、vから最寄りの家のある頂点までの距離とすると、D[u]+D[v]+c≦Tである辺は、利用可能である。
各クエリにおいては、利用可能な辺を用いてXとYが連結になるかを求めればよい。

D[v]はダイクストラ法で容易に求められるので、実装も簡単。

int N,M,K;
int A[202020],B[202020],C[202020];
vector<pair<int,int>> E[202020];
ll D[202020];

template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit(int num=um) {int i; FOR(i,num) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<202020> uf;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K;
	FOR(i,M) {
		cin>>A[i]>>B[i]>>C[i];
		A[i]--,B[i]--;
		E[A[i]].push_back({B[i],C[i]});
		E[B[i]].push_back({A[i],C[i]});
	}
	FOR(i,N) D[i]=1LL<<60;
	priority_queue<pair<ll,int>> Q;
	FOR(i,K) D[i]=0, Q.push({0,i});
	while(Q.size()) {
		ll co=-Q.top().first;
		int cur=Q.top().second;
		Q.pop();
		if(co!=D[cur]) continue;
		FORR2(e,c,E[cur]) if(D[e]>co+c) {
			D[e]=co+c;
			Q.push({-D[e],e});
		}
	}
	vector<pair<ll,int>> Es;
	FOR(i,M) Es.push_back({C[i]+D[A[i]]+D[B[i]],i});
	sort(ALL(Es));
	reverse(ALL(Es));
	
	int L;
	cin>>L;
	while(L--) {
		ll X,Y,T;
		cin>>X>>Y>>T;
		X--,Y--;
		while(Es.size()&&Es.back().first<=T) {
			uf(A[Es.back().second],B[Es.back().second]);
			Es.pop_back();
		}
		if(uf[X]==uf[Y]) {
			cout<<"Yes"<<endl;
		}
		else {
			cout<<"No"<<endl;
		}
	}
	
}

まとめ

このテクは使えそうなので覚えておきたい。