CSAcademy Round #45 : D. Chromatic Number

EよりDの方が難しかったようだ。
https://csacademy.com/contest/round-45/task/chromatic-number/

問題

N頂点の連結有向グラフが与えられる。
頂点1→Nの最短経路のうち、あるK個の頂点を選んだ時それらを通る経路数が最大となるものを選ぶとその経路数は何通りか。
また、同着でその経路数となるK頂点の組み合わせは何通りか。

解法

まずWarshal-Floyedなどで頂点間の最短経路を求めよう。
次にDPで各頂点を通る最大数の経路を数えていこう。
最大数を求めたら、再度DPを行いそのような最大数を実現するK個の頂点を数え上げていく。

なお、経路数を最大化するには余計な頂点の選択数を減らしたいので、まず必ず通ることが確定する頂点1・NをK個の頂点に含めておくと、始点終点周りのコーナーケースの処理が楽になる。

int N,M,K;
ll mat[303][303];
int ok[303][303],direct[303][303];
ll dp[303][303];
ll ma[303][303],pat[303][303];
ll mo=1000000007;

void solve() {
	int i,j,k,l,r,x,y,z; string s;
	
	cin>>N>>M>>K;
	FOR(x,N) FOR(y,N) mat[x][y]=(x==y)?0:1LL<<60;
	FOR(i,M) {
		cin>>x>>y>>r;
		mat[x-1][y-1]=mat[y-1][x-1]=r;
		direct[x-1][y-1]=direct[y-1][x-1]=r;
	}
	FOR(z,N) FOR(x,N) FOR(y,N) mat[x][y]=min(mat[x][y],mat[x][z]+mat[z][y]);
	
	FOR(x,N) FOR(y,N) ok[x][y]=(mat[0][x]+mat[x][y]+mat[y][N-1]==mat[0][N-1]);
	FOR(x,N) {
		dp[x][x]=1;
		vector<pair<ll,int>> V;
		FOR(y,N) V.push_back({mat[x][y],y});
		sort(ALL(V));
		FORR(v,V) {
			y=v.second;
			FOR(z,N) if(mat[x][z]+mat[z][y]==mat[x][y] && direct[y][z]==mat[y][z] && y!=z) dp[x][y]+=dp[x][z];
		}
	}
	
	ma[0][0]=pat[0][0]=1;
	ma[1][0]=pat[1][0]=1;
	FOR(i,K) {
		FOR(x,N) FOR(y,N) if(mat[0][x]+mat[x][y]==mat[0][y] && mat[x][y]>0) {
			if(ma[i+1][y]<ma[i][x]*dp[x][y]) {
				ma[i+1][y]=ma[i][x]*dp[x][y];
				pat[i+1][y]=0;
			}
			if(ma[i+1][y]==ma[i][x]*dp[x][y]) {
				(pat[i+1][y]+=pat[i][x])%=mo;
			}
		}
	}
	
	ll ret=0,ret2=0;
	FOR(i,N) if(mat[0][i]+mat[i][N-1]==mat[0][N-1] && ma[K][i]>0) {
		if(ret<ma[K][i]*dp[i][N-1]) {
			ret=ma[K][i]*dp[i][N-1];
			ret2=0;
		}
		if(ret==ma[K][i]*dp[i][N-1]) {
			ret2 += pat[K][i];
		}
	}
	
	cout<<ret<<" "<<ret2%mo<<endl;
}

まとめ

実装は難しくないけど頭が混乱する問題。