Codeforces #706 Div1 : D. BFS Trees

問題名が多少ヒントになっているか？
https://codeforces.com/contest/1495/problem/D

問題

連結無向グラフのMSTが頂点sに関するBFS Treeであるとは、MST上におけるsから各点までの最短距離が、元のグラフにおける最短距離と一致することを示す。

MSTのうち、頂点iに関しBFS Treeであり、かつ頂点jに関しBFS Treeであるものを、各頂点対(i,j)ごとに何通りあるか答えよ。

解法

頂点i,jの最短経路を1つ選び、そこに含まれる頂点・辺は選択必須としておく。
それ以外の頂点について、x及びyのいずれにも近づける辺があれば、そのうちの1つを選択すればよい。

int N,M;
const ll mo=998244353;
vector<int> V[400];
ll dp[400][400];
int D[400],vis[404];;
int S[404][404];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(y,N) FOR(x,N) S[y][x]=(y==x)?0:500;
	FOR(i,M) {
		cin>>x>>y;
		V[x-1].push_back(y-1);
		V[y-1].push_back(x-1);
		S[x-1][y-1]=S[y-1][x-1]=1;
	}
	FOR(k,N) FOR(x,N) FOR(y,N) S[x][y]=min(S[x][y],S[x][k]+S[k][y]);
	
	FOR(y,N) FOR(x,y+1) {
		ll ret=1;
		FOR(i,N) if(S[x][i]+S[i][y]==S[x][y]) D[S[x][i]]=i;
		ZERO(vis);
		FOR(i,S[x][y]+1) vis[D[i]]=1;
		FOR(i,N) if(vis[i]==0) {
			int pat=0;
			FORR(e,V[i]) if(S[e][x]==S[i][x]-1&&S[e][y]==S[i][y]-1) pat++;
			ret=ret*pat%mo;
		}
		
		dp[y][x]=dp[x][y]=ret;
	}
	
	FOR(y,N) {
		FOR(x,N) cout<<dp[y][x]<<" ";
		cout<<endl;
	}
	
}

まとめ

D問題の割にコードは短い。