Trip Compulsion (UVa Live Archive Asia - Site 10 (India) - 2009/2010)

頂点数N、辺数Rのグラフでstartからendまで行くパスを考える。そのようなパスの中で使用している辺の重みの最大値と最小値の差の最小値はいくらかという問題。
パスが無い場合はNO PATHと出力する。
2<=N<=2000
0<=R<=3000
1<=length<=2000000000

辺を重み順にソートしておいて、辺が軽い方から一つずつ削除していきながらクラスカル法をR回実行する。
全体のオーダーはO(R^2A)となる(Aはアッカーマン関数の逆関数)。
2分探索+dfs+枝刈りでも間に合うらしい。