TopCoder SRM 791 : Div2 Hard RandomDijkstraDiv2

こっちは簡単なんだけどね。
https://community.topcoder.com/stat?c=problem_statement&pm=16128&rd=18307

問題

各辺にコストが設定されたN頂点の完全有向グラフが与えられる。
ここでダイクストラ法を行い、各点について頂点0からの最短距離を求める手順を考える。
ダイクストラ法では未処理の点のうち距離が最短なものを選び、そこからの遷移で各点の最短距離を更新していく。
その際、以下2点の変更を加えると、正しくこのアルゴリズムが最短距離を計算する確率はどうなるか。

• 未処理のうち、等確率でランダムで点を選ぶ
• 処理済みの点はそれ以上距離を更新しない。

解法

ある点を処理する際は、既にその点が最短距離を保持していなければならない。
これは、最短距離の遷移元となる頂点が先に処理済みかどうかがわかればわかる。

そこで、
dp(処理済みの頂点のbitmask) := 処理状況そのような状態で、かつ処理済みの各点が最短距離を正しく持っている状態に遷移する確率
をdp(0)=1から初めてdp(2^N-1)まで計算していこう。

int D[20][20];
int M[20][20];
double dp[1<<15];

class RandomDijkstraDiv2 {
	public:
	double solve(int N, vector <int> G) {
		int i,x,y,z,j;
		FOR(y,N) FOR(x,N) M[y][x]=D[y][x]=G[y*N+x];
		FOR(z,N) FOR(x,N) FOR(y,N) M[x][y]=min(M[x][y],M[x][z]+M[z][y]);
		ZERO(dp);
		dp[0]=1;
		
		int mask;
		FOR(mask,1<<N) if(dp[mask]>0) {
			
			FOR(i,N) if((mask&(1<<i))==0) {
				int isok=0;
				if(i==0) isok=1;
				FOR(j,N) if((mask&(1<<j))&&M[0][j]+D[j][i]==M[0][i]) isok=1;
				
				if(isok) {
					dp[mask|(1<<i)]+=dp[mask]/(N-__builtin_popcount(mask));
				}
				
			}
		}
		
		return dp[(1<<N)-1];
		
	}
}

まとめ

このDiv1とDiv2の問題の分け方は珍しいね。