AtCoder ABC #319 : G - Counting Shortest Paths

なんで7問なんだろ。
https://atcoder.jp/contests/abc319/tasks/abc319_g

問題

N頂点の完全グラフから、M辺取り除いたグラフを考える。
1番の頂点からN番の頂点への最短経路は何通りか。

解法

D(v) := 頂点vの1番の頂点からの最短距離
dp(v) := 頂点vに最短経路で到達するパスの数
S(d) := D(v)=dである頂点の集合
とする。S(0)からBFSの要領で、S(1)、S(2)...と求めて行き、D(N)とdp(N)を確定させよう。

完全グラフに対し、M辺が通れない辺だとというように考えてみる。
S(n)がわかっているとき、D(v)が未確定の頂点vを総当たりして、S(n)のうち通れない辺が0個ならD(v)=n+1と確定する。
S(n+1)がわかったら、v∈S(n+1)に対しdp(v)を計算するが、dp(v)はu∈S(n)であるuに対するsum(dp(u))から、辺(u,v)が通れない辺であるようなuに対しdp(u)を引いていけばよい。

int N,M;
set<int> E[202020];
const ll mo=998244353;
ll dp[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		E[x-1].insert(y-1);
		E[y-1].insert(x-1);
	}
	set<int> alive,nex;
	FOR(i,N) if(i) alive.insert(i);
	nex.insert(0);
	dp[0]=1;
	while(nex.size()) {
		if(nex.count(N-1)) {
			cout<<dp[N-1]<<endl;
			return;
		}
		set<int> nex2;
		swap(nex,nex2);
		ll sum=0;
		FORR(c,nex2) sum+=dp[c];
		sum%=mo;
		FORR(a,alive) {
			int ok=0;
			FORR(b,nex2) {
				if(E[b].count(a)==0) {
					ok=1;
					break;
				}
			}
			if(ok) {
				nex.insert(a);
				dp[a]=sum;
				FORR(b,E[a]) if(nex2.count(b)) dp[a]+=mo-dp[b];
				dp[a]%=mo;
			}
		}
		FORR(n,nex) alive.erase(n);
	}
	cout<<-1<<endl;
	
}

まとめ

補グラフに関する問題、CFやyukicoderでも見た気がするな。
数え上げだったか覚えてないけど…。