JOI 2013 Taxis
Posted: 2015年6月18日(木) 01:05
始めまして、okapと申します。競技プログラミングを勉強中の高校生です。詳しくは自己紹介欄を見ていただけると嬉しいです。
貴掲示板は数年前に少しお世話になって以来ご無沙汰していたのですが、最近競技プログラミングの勉強を始め、いろいろ分からないことが出てきそうなのでまた皆さんのお世話になりたいと思いまして参りました。よろしくお願い申し上げます。
お聞きしたいのはこちらの問題です
申し訳ないことに解法の糸口すらつかめずにいて困っています。
この問題を読んで私が分かるのはグラフの問題かな？というぐらいです。（グラフも組んだことがありません。ごめんなさい）
ある町から別の町へのタクシーの運賃を重みとした最短経路を考えるべきなのではないかというところまで考えましたがそれ以上は分かりませんでした。
出来ましたら、指針と言いますかまずは切り口を教えてくださるとうれしいです。
あまりに出来が悪くて申し訳ないですが、よろしくお願いします。
※1トピックで1問の完答を目指していくつもりです。
貴掲示板は数年前に少しお世話になって以来ご無沙汰していたのですが、最近競技プログラミングの勉強を始め、いろいろ分からないことが出てきそうなのでまた皆さんのお世話になりたいと思いまして参りました。よろしくお願い申し上げます。
お聞きしたいのはこちらの問題です
オフトピック
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
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問の完答を目指していくつもりです。