torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

TopCoder, SRM 622, Division 1, Level 1 : BuildingRoutes

問題概要

 有向重み付き完全グラフ G = ( V, E ) と、正整数 T が与えられる。全ての頂点対 ( s, t ) について、s -> t の最短路を考える(ある ( s, t ) に対し最短路が複数存在する場合は、いずれも 0 でないような確率によって一本が選択される)。T 本以上の最短路に含まれる可能性がある辺の重みの総和を求めよ。
 |V| <= 50

解法

 それぞれの辺について、それを含む可能性がある最短路の数を求めることができれば問題を解くことができます。頂点対 ( s, t ) に対して、辺 ( i, j ) が s -> t 最短路に含まれる場合とは、d( s, t ) = d( s, i ) + c( i, j ) + d( j, t ) を満たす場合です。ここで、 d( a, b ) は a -> b 最短路のコスト、c( i, j ) は辺 ( i, j ) の重みを表します。各 ( i, j ) に対して ( s, t ) を総当りすれば、辺 ( i, j ) を含みうる最短路の数を求めることができます。このとき、任意の頂点対について頂点間の最短路の情報が必要になるので、予め Warshall-Floyd 法を用いて計算しておく必要があります(毎回求めるとやばい)。後は単純なループと条件分岐により、条件を満たす辺の重みの操作を求めれば問題を解くことができます。

コード

using VI = vector<int>;
using VVI = vector<VI>;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define ALL( c ) (c).begin(), (c).end()

class BuildingRoutes
{
public:
	int build( vector <string> dist, int T )
	{
		const int N = dist.size();

		VVI G( N );
		REP( i, 0, N )
		{
			transform( ALL( dist[i] ), back_inserter( G[i] ), bind( minus<int>(), _1, '0' ) );
		}

		REP( k, 0, N )
		{
			REP( i, 0, N )
			{
				REP( j, 0, N )
				{
					G[i][j] = min( G[i][j], G[i][k] + G[k][j] );
				}
			}
		}

		VVI counts( N, VI( N ) );
		REP( i, 0, N )
		{
			REP( j, 0, N )
			{
				REP( s, 0, N )
				{
					REP( t, 0, N )
					{
						counts[i][j] += G[s][t] == G[s][i] + dist[i][j] - '0' + G[j][t];
					}
				}
			}
		}

		int res = 0;
		REP( i, 0, N )
		{
			REP( j, 0, N )
			{
				if ( T <= counts[i][j] )
				{
					res += dist[i][j] - '0';
				}
			}
		}

		return res;
	}
};