JOI 2013 Taxis

[okap]

始めまして、okapと申します。競技プログラミングを勉強中の高校生です。詳しくは自己紹介欄を見ていただけると嬉しいです。
貴掲示板は数年前に少しお世話になって以来ご無沙汰していたのですが、最近競技プログラミングの勉強を始め、いろいろ分からないことが出てきそうなのでまた皆さんのお世話になりたいと思いまして参りました。よろしくお願い申し上げます。

お聞きしたいのはこちらの問題です

オフトピック

IOI 国は町 1 から町 N までの N 個の町からなり，町と町とは道路で結ばれている．IOI 国には K 本の道路があり，すべての道路は異なる 2 つの町を結んでいる．車は道路を双方向に自由に移動できるが，道路以外を通ってある町から別の町に行くことはできない．

IOI 国の町 1 に住む JOI 君は，町 N に住む祖母の家までタクシーで行くことにした．IOI 国にはタクシー会社 1 からタクシー会社 N までの N 個のタクシー会社がある．IOI 国のタクシー会社には次のような少々特殊な規則がある．

タクシー会社 i のタクシーには，町 i でのみ乗車できる．
タクシー会社 i のタクシーの運賃は，利用した距離によらず Ci である．
タクシー会社 i のタクシーは，乗車してから連続して最大 Ri 本の道路しか通ることができない．

たとえば R1 = 2 の場合，町 1 からタクシー会社 1 のタクシーに乗車すると，最大 2 本の道路しか通ることができないため，道路を 3 本以上通るためには途中の町でタクシーを乗り換える必要がある．

JOI 君は町以外の地点でタクシーに乗ったりタクシーから降りたりすることはできない．また，タクシー以外の移動手段を用いることもできない．JOI 君が町 N に到達するために必要な運賃の合計の最小値を求めるプログラムを作成せよ．

http://www.ioi-jp.org/joi/2013/2014-yo/ ... yo-t5.html

申し訳ないことに解法の糸口すらつかめずにいて困っています。
この問題を読んで私が分かるのはグラフの問題かな？というぐらいです。（グラフも組んだことがありません。ごめんなさい）
ある町から別の町へのタクシーの運賃を重みとした最短経路を考えるべきなのではないかというところまで考えましたがそれ以上は分かりませんでした。

出来ましたら、指針と言いますかまずは切り口を教えてくださるとうれしいです。
あまりに出来が悪くて申し訳ないですが、よろしくお願いします。

※1トピックで1問の完答を目指していくつもりです。

[みけCAT]

自分は(今いる町,今乗っているタクシーで移動できる残りの道路の数)の組をノードとし、
* 今乗っているタクシーで別の街に移動する
* 今いる町でタクシーに乗る
* ゴールの町で残りの道路の数を捨てる
という操作をエッジとしたグラフ上で、
同じノードの情報は高々1個しか同時にプライオリティキューに乗らない工夫をしたダイクストラ法で解いた気がします。

[okap]

ありがとうございます。ノードに情報を２つ持たせるのはクラスにするということですか？
無能すぎて恥ずかしいです

[okap]

現在位置u、残っている移動できる道路数をvとして
ここに至るまでの最小コストを
int dp[MAX_N][MAX_N]
とするというのはいかがですか...

[みけCAT]

ありがとうございます。ノードに情報を２つ持たせるのはクラスにするということですか？

情報を与えるとノードのID(添字)を返す関数を作るといいでしょう。
クラスにする必要はありません。

現在位置u、残っている移動できる道路数をvとして
ここに至るまでの最小コストを
int dp[MAX_N][MAX_N]
とするというのはいかがですか...

int型が4バイトの場合、およそ100MBの配列ですね。
u, vとの関係がわかりませんが、AOJでのメモリ制限は約250MBなので、これ単体で悪いとは言えません。
最短コストの求め方も考えて、それにあったやり方で保存するといいでしょう。

[okap]

>情報を与えるとノードのID(添字)を返す関数

イメージ出来ません。。。

[みけCAT]

>情報を与えるとノードのID(添字)を返す関数

イメージ出来ません。。。

n次元の情報を適当に1次元にマップするだけです。
例えば、

コード:

int get_id(int mati, int nokorinodourosuu) {
	return MAX_N * nokorinodourosuu + mati;
}

[okap]

1次元配列でid管理するのですか
エッジの貼り方が分かりません
参考にするサイトがありましたら教えていただきたいです。今まで隣接行列を二次元配列で表現するものしか見たことがなく、驚いています