Round Trip (AOJ 1324)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1324

問題

頂点数nで重み付きの辺がm本でさらに各頂点に通行料feeと高さhが与えられた有向グラフが与えられる。始点(fee=0,h=0)から終点(fee=0,h=1000)まで往復したい。ただし、通行料を取られるのは最初の1回目だけで2回目以降は素通りできる。また行きは今いる頂点より低い頂点には行けず、帰りは高い頂点にはいけない。往復するのに必要な最小のコストを求めよ。
2<=n<=50
0<=m<=n(n-1)
1<=fee<=1000
1<=h<=999
同じ高さの頂点は高々10個

解法

まず逆グラフを作っておく。行きは普通のグラフ、帰りは逆グラフを使って始点から終点へ行くことを考える。これをするには行きと帰りの今いる位置を記憶したDPを使えば良い。行きと帰りが違う高さの場合は低い方だけを考えれば良い。同じ高さの場合は使う頂点を決めて移動させれば良い。