torus711 のアレ

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

TopCoder, SRM 624, Division 1, Level 2 : DrivingPlans

問題概要

 N 頂点からなる連結な重み付き無向グラフが与えられる。重みは非負整数である。
 頂点を 1 から N で番号付けたとして、頂点 1 から頂点 N への最短経路(単純道とは限らない)の総数を求めよ。無限に存在する場合は -1 で示せ。


解法

 まず、経路総数が有限か否かを判定できなければなりません。ある長さの経路総数を無限にできる場合とは、その経路の途中(端点を含む)の頂点で、そこに接続する重み 0 の辺を往復できるときです。1 -> N までの最短経路上にそのような頂点が存在すれば、1 -> N の最短経路の総数を無限大にできます。もっと扱いやすい形で述べると、 重み 0 の辺を使った場合の N までの最短距離が、重み 0 の辺を使わない場合の N までの最短距離と等しいとき、N までの最短経路の総数が無限大になります。このように考えると、それぞれの条件付き最短距離は、頂点に属性を付加し ( 頂点、過去に重み 0 の辺を使ったか ) という組で頂点を区別するように拡張した Dijkstra 法によって求められることが分かります。
 また、経路総数は Dijkstra 法と同時に計算することができて、

  • 遷移先への最短距離を更新するとき -> 遷移先への経路総数を遷移元への経路総数で上書き
  • 遷移先への最短距離を更新できないが、暫定最短距離と等しいとき -> 遷移先への経路総数に遷移元への経路総数を足す

とすることで数え上げることができます。
 あとは、先程の条件に従って戻り値を変えれば問題を解くことができます。

コード

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int,int>;
using VPII = vector< pair<int,int> >;
template < typename T = int > using VT = vector<T>;
template < typename T = int > using LIM = numeric_limits<T>;

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

#define fst first
#define snd second

constexpr int INF = LIM<>::max() / 2;
constexpr int MOD = 1000000009;

class DrivingPlans
{
public:
	int count( int N, vector <int> A, vector <int> B, vector <int> C )
	{
		VT< VPII > G( N );
		REP( i, 0, A.size() )
		{
			A[i]--;
			B[i]--;

			G[ A[i] ].emplace_back( B[i], C[i] );
			G[ B[i] ].emplace_back( A[i], C[i] );
		}

		VVI distance( N, VI( 2, INF ) );
		distance[0][0] = 0;

		VVI counts( N, VI( 2, 0 ) );
		counts[0][0] = 1;

		using State = tuple< int, int, int >;
		priority_queue< State, VT< State >, greater< State > > que;
		que.push( make_tuple( 0, 0, 0 ) );

		while ( !que.empty() )
		{
			const int d = get<0>( que.top() );
			const int u = get<1>( que.top() );
			const int f = get<2>( que.top() );
			que.pop();

			if ( distance[u][f] < d )
			{
				continue;
			}

			FOR( e, G[u] )
			{
				const int v = e.fst;
				const int c = e.snd;

				const bool nf = f | ( c == 0 );
				if ( distance[u][f] + c < distance[v][ nf ] )
				{
					counts[v][ nf ] = counts[u][f];
					que.emplace( distance[v][ nf ] = distance[u][f] + c, v, nf  );
				}
				else if ( distance[u][f] + c == distance[v][ nf ] )
				{
					( counts[v][ nf ] += counts[u][f] ) %= MOD;
				}
			}
		}

		return distance[ N - 1 ][1] <= distance[ N - 1 ][0] ? -1 : counts[ N - 1 ][0];
	}
};