Same Distance Different Path

$1$から$N$への単純パスの本数を$P_N$と表すことにします．

$(N-1) \times \max_{1 \leq i,j \leq N} (D_{i,j}) < P_N$のとき， 鳩ノ巣原理より条件を満たすパスの組が必ず存在することが言えます．

よってこれ以降は$(N-1) \times \max_{1 \leq i,j \leq N} (D_{i,j}) \geq P_N$とします．

次に$P_N$を$N$を用いて実際に表すと以下の式となります．

• $P_N = \sum^{N-2}_{k=0} {}_{N-2}C_{k} \times k! = \sum^{N-2}_{k=0} {}_{N-2}P_{k}$

今$(N-1) \times \max_{1 \leq i,j \leq N} (D_{i,j}) \geq P_N$であるのでこれを変形して， $\max_{1 \leq i,j \leq N} (D_{i,j}) \geq P_N \div (N-1)$を得ます．
また，制約より$D_{i,j} \leq 10^5$であるので， $10^5 \geq P_N \div (N-1)$です．
この不等式を満たすような$N$は高々$12$であることが実際の計算により確かめることができます．

$P_{12} = 9864101$であるので，実際にあり得るパスをすべて列挙し， 長さが同じであるものが存在するかどうかを見ればよいです．

時間計算量は上で表した$P_N$を用いて$O(N \times P_N)$です． 厳密にはもっと厳しい評価や，実装の際の枝刈りができるため， 実際の計算回数はもう少し少なく抑えることができます．