JOI2013sp Day1 Bus Tour＜怪＞

はじめに

これはクソ解法…ということもないかもしれません。

本番でこれを書いてもいいかも？

ぱっとみめっちゃ辛くて、何が辛いって乗換が多いのが辛いです。

ただ、N<=1000であることから、バス運行路の組(i,j)についてそれぞれ見る必要のある乗換場所を考えます。

縦と縦or横と横で被っている場合はその被っている区間の端2か所だけ見ればよく、縦と横で被っている場合はその点だけ見ればよいです。

結論として、乗り換えが必要な組はそれぞれの(i,j)で最大4つなので、O(N²)で抑えられることが分かります。

本当はそれぞれの頂点に乗り換えの組をメモしたほうがいいんですが、面倒くさいのでさぼっても多分ばれません。頂点にメモするのは乗換の組のそれぞれのバスにすることにします。

これでダイクストラをする頂点が構成できたので、あとは適当にダイクストラすればよいです。

具体的に説明すると、a[x][y]=頂点(x,y)でバスに乗れる状態になった最初の時としてダイクストラをします。

境界判定が結構大変なので頑張る必要があります。