最終的に残されるのは、 11 から NN に至る経路と、 そこから分岐( 11 の手前や NN の奥に伸びるものも便宜上そう呼ぶ)する枝からなる全域木となります。 ここで、 11 から NN への経路を自由に決めると、これに含まれない街は適当に枝として繋げられることが分かります。

図

厳密には、与えられた道路を表すグラフにおいて全ての街の集合は連結であることから、ある時点において「経路につながっている街の集合」と「その時点で孤立している街の集合」の間には 11 本以上の道があります。 ここから 11 本だけ選べば閉路は生じないので、 11 から NN までの最短距離を変えずに 11 点を「つながっている集合」に移し替えることが可能です。 これを繰り返せば「全ての都市間を道路で行き来できる」条件は満たすことができます。

したがって、「 11 から NN まで、何都市かを通るループしない経路で最長のもの」を求めれば十分です。 全ての組み合わせおよび順列を考えることは制約からできませんが、「経路に含まれる街の集合(ここに属するものは後ろに繋げられない)」および「その時点で 11 からつながる経路上の一番先端にある街」の情報があれば十分で、 2N×N2^N \times N 個の配列で管理することが可能です。 具体的な遷移は

dp[S:dp[S: 経路に含まれる点の集合 ][k:][k: その時点でつなげた経路の一番先端の街 ]] =max(dp[T:S = max(dp[T:S から kk を抜いた集合 ][i]+dist[k][i])][i]+dist[k][i])

(( for SS に属する、かつ ii-kk 間の道が存在する ii ))

とすればよく、計算量は O(2N×N2)O(2^N \times N^2) です。

そして、「 1,N1,N を含む任意の集合」で「 NN が一番先端にある経路」すべてを見て、 最大値であるような長さがこの問題の答えとなります。