AtCoder Beginner Contest 342, E : Last Train

問題文

　https://atcoder.jp/contests/abc342/tasks/abc342_e

問題概要

　$1$ から $n$ で番号付けられた $n$ 個の駅があり，$m $ 種類の路線が運行されている．各路線は 6 個の整数 $l, d, k, c, a, b$ *1で説明され，その意味は，

• 駅 $u$ から駅 $v$ へ向かう路線は，
• 始発が時刻 $l$ であり，
• $d$ 分間隔で出発し，
• $k$ 本運行され，
• $c$ 分で目的地に到着する．

である．
　駅 $s$ から駅 $n$ に到達できる時刻の内最遅のものを $f( s )$ で表す．到達できない場合は $-\infty$ と定義する．
　$f( 1 ), f( 2 ), \dots, f( n - 1 )$ を求めよ．

制約

• $2 \leq n \leq 2 \times 10^5$
• $1 \leq m \leq 2 \times 10^5$
• $1 \leq l, d, k, c \leq 10^9$

解法

　$n - 1$ 個の駅それぞれについて独立に $f( * )$ の値を求めようとすると，経験的には一駅あたり $O( \log( n + m ) )$ 時間ぐらいしかかけられない感じがあり，ちょっと厳しそうです．というより，ちょっとよく考えると $f( u )$ を求めるとき，$u$ から直接移動できる駅 $v$ について $$t_d + c \leq f( v )$$ を満たす時刻 $t_d$ に出発する電車が乗れる電車で，$t_d$ の最大値が $f( u )$ なので，$f( u )$ は他の駅における解に依存しており，また，その依存関係は電車の移動方向と逆向きになっています．
　たまによく見るテクで，無向グラフにおいて各頂点から特定の頂点への最短路を求めたいときに，各頂点から最短経路アルゴリズムをそれぞれ走らせる代わりに，目的地から各頂点への最短路を求めることでアルゴリズムを走らせる回数を一回にして高速化するというのがあります．本問題でも，これと似たことをします．
　ということで逆順に値を決定していく方向で考えていきます．まず初期条件として $f( n ) = \infty$ です．値が確定した駅 $v$ に直接移動できる駅 $u$ について $f( u )$ を決定することを考えます．前述した（のと同値な）ように，乗れる電車は時刻 $f( v ) - c$ 以前に出発する電車です．もし $f( v ) - c < l$ ならば，乗れる電車はありません．乗れる電車があるとき，最も遅い出発時刻は
\begin{equation*}
l + d \times \min\left( k - 1, \frac{ ( f( v ) - c ) - l }{ d } \right)
\end{equation*}
です．式の気持ちとしては，始発時刻からの猶予を $d$ で割ることで，「何本目の電車に乗るか」を求めて，終電である $k - 1$ 本目 ($0$-indexed) との遅くない方を採用しています．こうして求まる解候補が暫定の解を改善するときに max-heap に突っ込むようにすることで，Dijkstra 法のように（あるいは Dijkstra 法そのもので）各頂点における解を求めていくことができます．Dijkstra 法と言えば最短経路アルゴリズムですが，$f( n ) = \infty$ に「近い」時刻から決定していくのである意味最短経路的であると言える気がします．
　アルゴリズムの定義とかは脇に置いておいて，実装及び動作原理は Dijkstra 法と同じなので，計算量としては（全体で） $O( n + m \log n )$ 時間となります．

コード

constexpr auto INF = LIM< LL >::max() / 2;

int main()
{
	IN( int, N, M );
	using Edge = tuple< LL, LL, LL, LL, int >;
	auto G = make_vector< Edge >( N, 0, Edge() );
	REP( M )
	{
		IN( int, l, d, k, c, u, v );
		--u, --v;
		G[v].EB( l, d, k, c, u );
	}

	VLL results( N, -INF );
	results[ N - 1 ] = INF;

	priority_queue< pair< LL, int > > que;
	que.EM( INF, N - 1 );

	while ( !que.empty() )
	{
		const LL time = que.top().fst;
		const int v = que.top().snd;
		que.pop();

		if ( time != results[v] )
		{
			continue;
		}

		FOR( e, G[v] )
		{
			const LL l = get< 0 >( e );
			const LL d = get< 1 >( e );
			const LL k = get< 2 >( e );
			const LL c = get< 3 >( e );
			const int u = get< 4 >( e );

			if ( !( l <= time - c ) )
			{
				continue;
			}

			if ( const int nth = min( k - 1, ( ( time - c ) - l ) / d );
					chmax( results[u], l + d * nth ) )
			{
				que.EM( results[u], u );
			}
		}
	}

	REP( i, N - 1 )
	{
		if ( results[i] == -INF )
		{
			cout << "Unreachable\n";
		}
		else
		{
			cout << results[i] << '\n';
		}
	}

	cout << flush;

	return 0;
}

*1:書くのが面倒だったので端折っていますが，正確には添字が付きます．原文参照のこと．