入力の項にて，G_x, G_yが書かれているのは，2行目ではなくて3行目だと思います．

修正しました．ありがとうございます．

S_j=T_iを満たすようなi,j(1≦i<j≦N)が存在しないことは保証されますか

制約の記述に不備がありました．
そのようなi,jが存在しないことは保証されます．

[16:18]記述を修正しました．

入力形式における P(i,j) はすべて P(j,i) の誤りですか

大変申し訳ございません．
その通りです．

[16:05]記述を修正致しました．