Long Distance Taxi (AOJ 1318)

AOJ Online Judge

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

問題

辺数nのグラフが与えられる。srcからdestまで行きたいのだが途中でLGPガスを補給する必要がある。車の燃料タンクにはcap分だけLGPガスを搭載できる。またLGPガスステーションはグラフ中にm個ある。srcからdestまでの最短距離を求めよ。
1<=n<=3000
1<=m<=300
1<=cap<=200

解法

拡張ダイクストラするだけ。頂点数は最大6000個になることに注意。