AOJ 0575 Festivals in JOI Kingdom

問題

日本語なので本文参照（http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0575）

制約条件

N, Q≦100000
M≦200000
K≦N

方針

まずは、それぞれのノードについて、
お祭りが開催されているノードまでの最短距離を求める。

これは、Dijkstra法で、初期ノードをお祭りの開催されている全ノードとすればいい。

次に、距離の遠い順にノードをマージしていく。
ノードには、そのノードに属するクエリの番号の集合をもたせておき、
同じ番号のクエリをもつ集合がはじめてマージされたとき、
その時点での距離が、そのクエリを達成するのに必要な最長距離になる。

同じ番号がマージされたら、その番号は消してしまったよい。

最悪計算量悪そう、、、と思ったが、
サイズの大きいほうに小さいほうをマージすれば、そんなことはなさそうだった。

サイズnの集合を作るのに必要な挿入の回数をT(n)としたら、
T(n)≦max[i

ソースコード

const int MX = 100000;

int n, m, k, q;
vector<vector<pi> > e;

int d[MX], p[MX], ans[MX];
set<int> s[MX];

int root(int x){
	if(x == p[x]) return x;
	return p[x] = root(p[x]);
}

int main()
{
	scanf("%d%d%d%d", &n, &m, &k, &q);
	e.resize(n);
	
	vector<pair<int, pi> > es;
	
	rep(i, m){
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		a--; b--;
		e[a].pb(mp(b, c));
		e[b].pb(mp(a, c));
		
		es.pb(mp(0, mp(a, b)));
	}
	
	{
		priority_queue<pi> q;
		rep(i, k){
			int t;
			scanf("%d", &t);
			q.push(mp(0, t - 1));
		}
		
		rep(i, n) d[i] = inf;
		while(!q.empty()){
			int c = q.top().second, cost =- q.top().first;
			q.pop();
			
			if(d[c] <= cost) continue;
			d[c] = cost;
			
			rep(i, e[c].size()){
				int to = e[c][i].first;
				int ncost = cost + e[c][i].second;
				if(d[to] > ncost) q.push(mp(-ncost, to));
			}
		}
	}
	
	rep(i, q){
		int a, b;
		scanf("%d%d", &a, &b);
		a--; b--;
		s[a].insert(i);
		s[b].insert(i);
	}
	
	rep(i, n) p[i] = i;
	rep(i, m){
		es[i].first = -min(d[es[i].second.first], d[es[i].second.second]);
	}
	sort(all(es));
	
	rep(i, m){
		int a = root(es[i].second.first);
		int b = root(es[i].second.second);
		
		if(a == b) continue;
		if(s[a].size() < s[b].size()) swap(a, b);
		
		each(j, s[b]){
			if(s[a].count(*j)){
				ans[*j] = -es[i].first;
				s[a].erase(*j);
			}
			else s[a].insert(*j);
		}
		p[b] = a;
	}
	
	rep(i, q) printf("%d\n", ans[i]);
	
	return 0;
}