Same Distance Different Path

2 secs 1024 MB
RedSpica's icon RedSpica

問題文

NN頂点からなる完全無向グラフが与えられます.便宜上ii番目の頂点を頂点iiと呼びます.
また,各辺の長さはN×NN \times N行列DDによって与えられ, 頂点iiと頂点jjを結ぶ辺の長さはDi,jD_{i,j}です.

ここで以下の条件を満たす異なる22つの単純パスが存在するかどうかを判定してください.

  • 頂点11から頂点NNへのパスであって,グラフ上のその22つのパスの長さが等しい

より厳密には以下の条件を全て満たす異なる22つの整数列AABBが存在するかどうかを判定してください.

  • AAの各要素は11以上NN以下の整数で,相異なる
  • BBの各要素は11以上NN以下の整数で,相異なる
  • A1=B1=1A_1=B_1=1
  • AAの項数をnnBBの項数をmmとすると,An=Bm=NA_n=B_m=N
  • i=1n1DAi,Ai+1=i=1m1DBi,Bi+1\sum^{n-1}_{i=1}D_{A_i,A_{i+1}} = \sum^{m-1}_{i=1}D_{B_i,B_{i+1}}

ただし,22つの数列A,BA,Bが異なるとは,以下の条件のうち少なくとも11つを満たすときにいいます.

  • AAの項数とBBの項数が異なる
  • ある整数iiが存在してAiBiA_i \neq B_iとなる

制約

  • 2N2×1022 \leq N \leq 2 \times 10^2
  • 0Di,j1050 \leq D_{i,j} \leq 10^5
  • i=jDi,j=0i=j \Rightarrow D_{i,j}=0
  • ijDi,j>0i \neq j \Rightarrow D_{i,j}>0
  • Di,j=Dj,iD_{i,j}=D_{j,i}
  • 入力される値はすべて整数である

入力

入力は以下の形式で標準入力から与えられます.

NN
D1,1D_{1,1}D1,2D_{1,2} \cdots D1,ND_{1,N}
D2,1D_{2,1}D2,2D_{2,2} \cdots D2,ND_{2,N}
\vdots
DN,1D_{N,1}DN,2D_{N,2} \cdots DN,ND_{N,N}

出力

条件を満たすものが存在するときはYesを, そうでないときはNoを出力せよ.

サンプル

入力1
3
0 1 3
1 0 2
3 2 0
出力1
Yes

22つのパスとして{1,3}\{1,3\}{1,2,3}\{1,2,3\}を取るとこれは条件を満たします.

入力2
4
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
出力2
Yes

22つのパスとして{1,2,3,4}\{1,2,3,4\}{1,3,2,4}\{1,3,2,4\}を取るとこれは条件を満たします. 他にも条件を満たすパスの組は複数存在します.

入力3
4
0 1 2 4
1 0 8 16
2 8 0 32
4 16 32 0
出力3
No

提出


Go (1.21)