No.2 Taxis


時間制限:$2.0sec$ / メモリ制限:$256MB$

問題文

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$ に到達するために必要な運賃の合計の最小値を求めるプログラムを作成せよ.

入力

入力は $1 + N + K$ 行からなる.

1 行目には,2 つの整数 $N$,$K$ $(2 ≦ N ≦ 5000, N - 1 ≦ K ≦ 10000)$ が空白を区切りとして書かれている.これは,IOI 国が $N$ 個の町からなることと,IOI 国の道路の本数が $K$ 本であることを表す.

続く $N$ 行のうちの $i$ 行目 $(1 ≦ i ≦ N)$ には,2 つの整数 $Ci, Ri$ $(1 ≦ Ci ≦ 10000, 1 ≦ Ri ≦ N)$ が空白を区切りとして書かれている.これは,タクシー会社 $i$ のタクシーの運賃が $Ci$ で,乗車してから連続して最大 $Ri$ 本の道路しか通ることができないことを表す.

続く $K$ 行のうちの $j$ 行目 $(1 ≦ j ≦ K)$ には,異なる 2 つの整数 $Aj, Bj$ $(1 ≦ Aj < Bj ≦ N)$ が空白を区切りとして書かれている.これは,町 $Aj$ と町 $Bj$ との間に道路が存在することを表す.同じ $(Aj, Bj)$ の組が 2 回以上書かれていることはない.

与えられる入力データにおいては,どの町から別のどの町へもタクシーを乗り継いで行くことができることが保証されている.

出力

JOI 君が町 1 から町 N まで行くのに必要な運賃の合計の最小値を表す整数を 1 行で出力せよ.

入出力例

入力1

6 6
400 2
200 1
600 3
1000 1
300 5
700 4
1 2
2 3
3 6
4 6
1 5
2 4
出力1

700

この入出力例でJOI 君が最小の運賃で町 $6$ に到達するには,以下のようにする.

  • 町 $1$ からタクシーに乗って町 $5$ に行く. (運賃 $400$)
  • 町 $5$ からタクシーに乗って町 $6$ に行く. (運賃 $300$)

JOI 君がこのようなルートを通った場合の運賃の合計は $400 + 300 = 700$ であるので,$700$ を出力する.





解説


この問題のように,「いくつかの頂点 (町) があり,頂点と頂点との間が辺 (道路) で結ばれている」ようなデータ構造は, グラフ と呼ばれる.この問題は,グラフの操作に習熟しているかを問う問題であった.

まずこの問題で重要なことは,町 i から町 j までタクシーを途中で乗り換えることなく行けるかどうかを判定することである.判定方法のひとつに, Warshall-Floyd 法 というものがある.これは一般のグラフについて,全頂点間の最短路を O(N3) で求めるものである.ただし,この問題においては,Nの最大値が 5000 と大きいため, O(N3) の解法では十分高速に解答を求めることができない.

そこで,より単純に 幅優先探索 を全ての頂点について行うことを考える.一回の幅優先探索は O(K) で行うことができ,N 個の頂点についてこれを行うため全体で O(NK) で行うことができる.この問題では K の最大値が 10000 とやや小さいため,この方法を用いることで十分高速に求めることができる.

さて,これで町 i から町 j までタクシーを途中で乗り換えることなく行けるかどうかを全ての町 i, j 間について判定することができた.次に,これをもとに,町 1 から町 N まで行く場合の運賃の合計の最小値を求める.

それを行うために,町を頂点として, 「町 i から町 j までタクシーを途中で乗り換えることなく行ける場合,町 i から町 j にコスト Ciの辺がある」 ような,新たな有向グラフ G を作成する.グラフ G 上でコスト C の辺を通ることは,運賃 C のタクシーに乗って町間を移動することに相当する.このグラフ G 上での町 1 から町 N までの最短経路 (コストの合計が最小の経路) が,JOI 君が町 1 から町 N までタクシーで移動する際に運賃の合計が最小となるような経路となる.よって,グラフ G 上で町 1 から町 N までの最短経路を Dijkstra 法 などで求めれば,コストの合計がこの問題に対する答えとなる.

解説中に登場した 3 つのアルゴリズム: Warshall-Floyd 法 幅優先探索 Dijkstra 法 は,グラフを扱う上で重要なアルゴリズムであるので,各自習得しておくのが望ましい.