問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう!
前問では、グラフのある始点、経由点、終点を結ぶ距離を求めました。本問では、この始点、経由点、終点の 3 点の距離と始点、終点の 2 点の距離を比較してみましょう。
1, ..., N の番号がついた N 個の頂点とそれらをつなぐ枝からなる有向グラフを考えます。ただし、自己ループと多重辺は考えません。
M 本の重み付き有向枝が与えられます。その後、Q 個の頂点の組 (d, e, f) が与えられます。各組について、頂点 d を出発し、頂点 e を経由して、頂点 f へ向かう枝数 2 の経路 (d → e → f) の距離と頂点 d を出発し頂点 f へ直接向かう枝数 1 の経路 (d → f) の距離を比較し、前者のほうが短ければ transit
、後者のほうが短ければ direct
、同じ距離ならば same
と出力してください。 ただし、経由する場合としない場合のどちらの場合でも経路が存在しない場合も same
と出力してください。
ただし、経路(枝の集合)の距離とはその経路を構成する枝の重みの和とします。ある頂点からその頂点自身へ移動する場合は、その区間の重みを 0 とします。また経路が存在しない場合は、その距離を 999
としてください。
N M Q
a_1 b_1 c_1
...
a_M b_M c_M
d_1 e_1 f_1
...
d_Q e_Q f_Q
合計 Q 行出力してください。j (1 ≦ j ≦ Q) 行目には、経路 d_j → e_j → f_j と経路 d_j → f_j を比較した結果を出力してください。
また末尾に改行を入れ、余計な文字、空行を含んではいけません。
すべてのテストケースにおいて、以下の条件をみたします。
3 2 2
1 2 5
2 3 1
1 2 3
3 2 1
transit
same
5 6 5
1 2 4
1 3 9
2 4 1
4 5 3
5 2 3
4 2 7
2 4 5
2 2 2
2 4 2
1 1 3
4 5 5
transit
same
direct
same
same