問題概要
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]; } };