駅 \(i\) にいるときに今まで訪れた駅の集合が \(S\) である場合の最長距離を \(D(i, S)\) とすると,

\[D(i, S) = \max_{j \in V_i} \{ D(j, S \setminus \{ j \}) + C_{i,j} \}\]

となる. ただし, \(V_i\) は \(i\) に隣接する駅の集合, \(C(i, j)\) は \(i, j\) 間の距離である.

これを DP で求める.