EducationalCF51 F - The Shortest Statement

Codeforces
問題

重み付き連結無向グラフが与えられる
またq個のクエリが与えられ、各クエリで頂点uiとvi間の最短距離を出力する

1 <= 頂点数n、辺数m、クエリ数q <= 10^5
m-n <= 20
1 <= 辺の重み <= 10^9

解法

制約より、グラフから辺をm-n+1本適切に削れば木になる
この木をT、削った辺をMとする
Tにおける2点間の距離は、適当な頂点を根とした根付き木と見なしてLCAを求めることで高速に求めることができる
(頂点a,bのLCAをx、根から頂点aへの距離をdt[a]などとすると、ab間の距離は(dt[a]-dt[x])+(dt[b]-dt[x])となる)
一方Mの各辺が繋ぐ頂点の集合をSとすると、Sに含まれる2頂点間の実際の最短距離は、"M" と "Tでの距離" という2種類の辺を貼ったグラフにワーシャルフロイド法を用いれば求められる
これらを組み合わせてクエリに答える

具体的には、まず答えをTでの距離で初期化し、Sに含まれる2頂点を経由する(∴Mに含まれる辺も使う)ときの最短距離で答えを更新していく
2頂点a,b間の最短距離は、Sに含まれる2頂点x,yを経由するとき、
(Tにおけるaからxまでの距離) + (Sだけで作ったグラフにおけるxからyまでの最短距離) + (Tにおけるyからbまでの距離)
となる

実装

大体の流れはコードに書いてあるコメントの通り
最初に木を作るのはUnionFindでやった

TLEについては、
m-n <= 20よりSの頂点数は最大42
クエリごとにこれの2乗(≒2*10^3)通りを全部試すことになるからその時点で10^5 * 2*10^3 = 2*10^8
ここにlogN(≒20)を付けると落ちる

class LCA {
private:
	static const int MAXLOGV = 17;
	static const int MAXV = 1<<MAXLOGV;
	int root;
	vector<int> e[MAXV];
	int par[MAXLOGV][MAXV], dep[MAXV];

public:
	void dfs(int v, int p, int d) {
		par[0][v] = p;
		dep[v] = d;
		for (int i=0; i<e[v].size(); i++)
			if (e[v][i]!=p) dfs(e[v][i], v, d+1);
	}
	void add(int from, int to) {
		e[from].push_back(to);
		e[to].push_back(from);
	}
	void init(int N, int ROOT) {
		root = ROOT;
		dfs(root, -1, 0);
		for (int k=0; k<MAXLOGV-1; k++)
			for (int v=0; v<N; v++) {
				if (par[k][v]<0) par[k+1][v] = -1;
				else par[k+1][v] = par[k][par[k][v]];
			}
	}
	int lca(int u, int v) {
		if (dep[u]>dep[v]) swap(u,v);
		for (int k=0; k<MAXLOGV; k++)
			if ((dep[v]-dep[u])>>k&1) v = par[k][v];
		if (u==v) return u;
		for(int k=MAXLOGV-1; k>=0; k--)
			if (par[k][u]!=par[k][v]) {
				u = par[k][u];
				v = par[k][v];
			}
		return par[0][u];
	}
};

struct UF {
	vector<int> p;
	UF(int n) : p(n, -1) {};
	bool unite(int u, int v) {
		if ((u = find(u)) == (v = find(v))) return false;
		if (p[u] > p[v]) swap(u, v);
		p[u] += p[v]; p[v] = u;
		return true;
	}
	bool same(int u, int v) { return find(u) == find(v); }
	int find(int u) { return p[u] < 0 ? u : p[u] = find(p[u]); }
	int usize(int u) { return -p[find(u)]; }
};

int n, m, a, b, c, q, dt[114514], ds[114514][44], d[44][44];
LCA lc;
UF uf(114514);
vector<pair<int,int> > e[114514];
vector<pair<pair<int,int>,int> > es;
set<int> com;
map<int,int> t;
vector<int> r(44);

void rec(int v, int p, int dis) {
	dt[v] = dis;
	each(i,e[v]) if (i.first!=p) rec(i.first, v, dis+i.second);
}

int dist(int x, int y) {
	return dt[x] + dt[y] - dt[lc.lca(x,y)]*2;
}

signed main() {
	cin >> n >> m;
	rep(i,m) {
		cin >> a >> b >> c;
		a--, b--;
		if (uf.same(a,b)) {
			es.push_back({{a,b},c});
			com.insert(a), com.insert(b);
		} else {
			e[a].push_back({b,c}), e[b].push_back({a,c});
			lc.add(a,b);
			uf.unite(a,b);
		}
	}
	// 根付き木の根(頂点0)から各点への距離を求める
	rec(0,-1,0);
	// 余った辺が繋ぐ頂点たちの番号を圧縮
	lc.init(n,0);
	int num = 0;
	each(i,com) t[i] = num, r[num++] = i;
	// このnum個の頂点間の最短距離を求める
	rep(i,num) rep(j,num) if (i!=j) d[i][j] = linf;
	each(i,es) {
		a = i.first.first, b = i.first.second, c = i.second;
		int ta = t[a], tb = t[b];
		d[ta][tb] = d[tb][ta] = c;
	}
	rep(i,num) reps(j,i+1,num) {
		int dis = dist(r[i],r[j]);
		chmin(d[i][j],dis), chmin(d[j][i],dis);
	}
	rep(k,num) rep(i,num) rep(j,num)
		chmin(d[i][j], d[i][k]+d[k][j]);
	// 各頂点とnum個の頂点間の距離を事前に求めておく(ここをクエリごとにやってるとTLE)
	rep(i,n) rep(j,num) ds[i][j] = dist(i,r[j]);
	// クエリに答える
	cin >> q;
	while (q--) {
		cin >> a >> b;
		a--, b--;
		int res = dist(a,b);
		rep(i,num) rep(j,num) if (i!=j)
			chmin(res, ds[a][i] + d[i][j] + ds[b][j]);
		cout << res << endl;
	}
}

なっが