スタートを \(s\) とする.

\(T\) 分以内に \(s \rightarrow P \rightarrow Q \rightarrow s\) とたどれるなら2人はずっと一緒にいられる.

\(T\) 分以内に \(s \rightarrow P \rightarrow s\) か \(s \rightarrow Q \rightarrow s\) のどちらかたどれない場合は条件は満たさない.

そうでない場合は雪男君が \(P\) に行き, 雪女さんが \(Q\) に行くとする. \(s \rightarrow P\) と \(s \rightarrow Q\) のルートが分かれた後に合流することはない (合流点は同じルートをたどった方がいい) ので, ある地点で分かれてそれぞれ \(P, Q\) に行き, 帰りもまたある地点で合流して戻るのがいい. (ある地点は \(s\) も含む)

行きの分岐点と帰りの合流点を総当りして一緒にいれる時間 (\(T\) から1人でいなければいけない時間を引いた時間) の最大値を求める.

計算にあたっては \(s, P, Q\) から各地点への最短距離をあらかじめ Dijkstra 法で計算しておけばいい.