会津大学オンラインジャッジ Festivals in JOI Kingdom - sinapusu2002 @ ウィキ

会津大学オンラインジャッジ問575
JOI 国のお祭り事情(Festivals in JOI Kingdom)

お祭りを題材にしたグラフ理論の問題。

時折思い出しては挑戦するも答えがわからず。
３年間の間で10日くらいは考えたかもしれない。
グラフを祭りから一番遠くの点からつなげて、つながってる点に新たにつなげるときはつながってない点と繋がってる点の中の一番祭りに近い点をつなげていけばいいと気づいたら何とか解けた。
つまり存在しない線を書き足すのである。
正攻法かは不明。
最初は再帰でサクッと書くも、再帰が深くなりすぎてエラー。
仕方ないのでスタックで置き換えた。
難しい。

多分正攻法ではないような気もする。

解法
まずすべての辺を削除し、点を封鎖する。
祭りから遠い点から順番に開封していき、今開封中の点と開封済みの点が削除した辺でつながっていたらつなぐ。
ただし開封済みの点が森をなしているときは、森の中で一番祭りに近い点と今開封中の点に新しい辺を書き足してつなぐ。
同じ森とは２本以上の辺ではつながない。
こうするとグラフを木構造として再構築できる。
後は木を根元から走査していけば解となる。

新しい辺を書き足すというのに気付くのに３年かかったわけである。
ぽんこっつだな私の頭。

#include<stdio.h>
#include<vector>
#include<set>
#include<map>
#include<string.h>
#include<queue>
#include<algorithm>
#include<queue>


struct S{
	int no,len;
	bool operator<(const S& s)const{
		return len>s.len;
	}
};
 
struct E{
	int a,b;
};

std::map<int,std::map<int,int> > qs;
std::vector<E> qsLog;


const int LIMIT=100001; 

std::vector<S> con[LIMIT];
std::vector<int> con2[LIMIT];
int n,m,q,k;
int lens[LIMIT];
int oya[LIMIT];


int count=0;
std::map<int,int> noToCount;
bool noHit[LIMIT];
std::map<int,int> countLog;

void d(){
 	S s,s2;
	s.len=s.no=0;
	memset(lens,-1,sizeof(lens));
	std::priority_queue<S> pq;
	pq.push(s);
	while(!pq.empty()){
		s=pq.top();
		pq.pop();
		if(lens[s.no]!=-1)continue;
		lens[s.no]=s.len;
		for(int i=0;i<con[s.no].size();i++){
			s2=con[s.no][i];
			s2.len+=s.len;
			if(lens[s2.no]!=-1 && lens[s2.no]<=s2.len)continue;
			pq.push(s2);
		}
	}
	//for(int i=0;i<=n;i++){
	//	printf("%d %d\n",i,lens[i]);
	//}
} 

int oyaSearch(int no,int no2){
	if(oya[no]==no2){
		return -1;
	}
	if(oya[no]==no){
		return no;
	}
	int re=oyaSearch(oya[no],no2);
	if(re!=-1)oya[no]=re;
	return re;
} 

int oyaSet(int no,int no2){
	if(oya[no]==no2){
		return no2;
	}
	
	if(oya[no]==no){
		oya[no]=no2;
		return no2;
	}
	int re=oyaSet(oya[no],no2);
	oya[no]=re;
	return re;
}

void print(std::vector<int> stc){
	printf("\n");
	for(int i=0;i<stc.size();i++){
		printf("%d ",stc[i]);
	}
}

void saiki(int no){
 	std::vector<int> stc1,stc2,stc3;
	stc1.push_back(no);
	stc2.push_back(0);
	stc3.push_back(0);
	noToCount[no]=0;
 	while(stc1.empty()==false){
		no=stc1.back();
 		int inc=stc2.back();
		noHit[no]=true;
		
		
		
		std::map<int,int>::iterator it,it2;
		for(it=qs[no].begin();it!=qs[no].end();it++){
 			int a=no;
 			int b=(*it).first;
			if(noHit[b]==false)continue;
 			it2=countLog.lower_bound(noToCount[b]);
			//printf("<%d %d %d>",(*it2).first,(*it2).second,lens[(*it2).second]);
			int len1=lens[a];
			int len2=lens[(*it2).second];
 			int len3=len1<len2?len1:len2;
 			qs[a][b]=len3;
			qs[b][a]=len3;
		}
			
 		
		
 		if(inc+1>con2[no].size()){
			int count2=stc3.back();
			countLog.erase(count2);		
 			stc1.pop_back();
			stc2.pop_back();
			stc3.pop_back();
 			if(stc1.empty()==false){
				int no=stc1.back();
				int count2=stc3.back();
				
				
				countLog.erase(count2);
 				count++;
				countLog[count]=no;
				stc3.pop_back();
				stc3.push_back(count);
			}
		}else{
			count++;
			stc1.push_back(con2[no][inc]);
			stc2.pop_back();
			stc2.push_back(inc+1);
			stc2.push_back(0);
			stc3.push_back(count);
			countLog[count]=stc1.back();
			noToCount[con2[no][inc]]=count;
			//print(stc1);
			//print(stc2);
			//print(stc3);
			//printf(" ok\n\n");
		}
		
	}
} 

int main(){
	scanf("%d %d %d %d",&n,&m,&k,&q);
	S s,s2;
	for(int i=0;i<m;i++){
		int a,b;
		scanf("%d %d %d",&a,&b,&s.len);
		s.no=b;
		con[a].push_back(s);
		s.no=a;
		con[b].push_back(s);
	}
	for(int i=0;i<k;i++){
		scanf("%d",&s.no);
		s.len=0;
	con[0].push_back(s);
	}
	d();
 	
 	E e1;
	for(int i=0;i<q;i++){
		int a,b;
		scanf("%d %d",&a,&b);
		qs[a][b]=0;
		qs[b][a]=0;
		e1.a=a;
		e1.b=b;
		qsLog.push_back(e1);
 	}
	std::vector<S> cityLen;
	for(int i=1;i<=n;i++){
		s.no=i;
		s.len=lens[i];
		cityLen.push_back(s);
	}
	std::sort(cityLen.begin(),cityLen.end());
		
	for(int i=1;i<=n;i++)oya[i]=-1;
	int start=0;
	for(int i=0;i<n;i++){
		s=cityLen[i];
		oya[s.no]=s.no;
		for(int j=0;j<con[s.no].size();j++){
			s2=con[s.no][j];
			if(oya[s2.no]==-1)continue;
			int re=oyaSearch(s2.no,s.no);
			if(re!=-1){
				con2[s.no].push_back(re);
			}
			oyaSet(s2.no,s.no);
		}
		start=s.no;
	}
	
	//printf("//////\n");
	
	//for(int i=0;i<=n;i++){
		//for(int j=0;j<con2[i].size();j++){
		//	printf("%d %d\n",i,con2[i][j]);
		//}
	//}
	for(int i=1;i<=n;i++){
		noHit[i]=false;
	}
	saiki(start);
	
	for(int i=0;i<qsLog.size();i++){
		E e1=qsLog[i];
		int a=e1.a;
		int b=e1.b;
		printf("%d\n",qs[a][b]);
	}
}