結果

問題 No.3482 Quod Erat Demonstrandum
コンテスト
ユーザー moon17
提出日時 2026-03-27 22:10:57
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 1,077 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 500 ms
コンパイル使用メモリ 85,144 KB
実行使用メモリ 152,280 KB
最終ジャッジ日時 2026-03-27 22:11:27
合計ジャッジ時間 29,281 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 33 WA * 12
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from collections import*
def f(s):
  q=deque([s])
  vs=[-1]*n
  vs[s]=0
  while q:
    p=q.popleft()
    for v in g[p]:
      if vs[v]==-1:
        vs[v]=vs[p]+1
        q+=v,
  return vs
def find(x):
 q=[]
 while uf[x]^x:q+=x,;x=uf[x]
 for p in q:uf[p]=x
 return x
def unite(x,y):
 x,y=find(x),find(y)
 if x^y:uf[x]=y
for _ in range(int(input())):
  n,m=map(int,input().split())
  abc=[[*map(int,input().split())]for _ in range(m)]
  uf=[*range(n)]
  d=s=0
  g=[[]for _ in range(n)]
  for a,b,c in abc:
    a-=1;b-=1
    if c==1:
      unite(a,b)
      g[a]+=b,
      g[b]+=a,
  u,v=find(0),find(n-1)
  if find(0)==find(n-1):
    s=1
  s0=f(0)
  sn=f(n-1)
  us=[]
  vs=[]
  ms0=msn=1<<60
  for a,b,c in abc:
    a-=1;b-=1
    la,lb=find(a),find(b)
    if c==2:
      if (la,lb)==(u,v):
        ms0=min(ms0,s0[u])
        msn=min(ms0,sn[v])
        d=1
      elif (la,lb)==(v,u):
        ms0=min(ms0,s0[v])
        msn=min(ms0,sn[u])
        d=1
  if s>d:
    print('Same')
    print(s0[n-1])
  elif s<d:
    print('Different')
    print(ms0+msn+1)
  else:
    print('Unknown')
0