結果

問題 No.416 旅行会社
ユーザー Tawara
提出日時 2016-08-27 08:11:01
言語 PyPy2
(7.3.15)
結果
AC  
実行時間 770 ms / 4,000 ms
コード長 522 bytes
コンパイル時間 2,166 ms
コンパイル使用メモリ 76,800 KB
実行使用メモリ 156,060 KB
最終ジャッジ日時 2024-12-14 20:02:41
合計ジャッジ時間 10,780 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

X=xrange;I=lambda:map(int,raw_input().split())
N,M,Q=I()
O=10**6;R=[0]*N;A=[0]*N;B=set()
L=[[] for i in X(N)]
E=[I()for i in X(M+Q)]
for i in X(Q):f,t=E[M+i];B|={f+t*O};B|={f*O+t}
for i in X(M):
	f,t=E[i]
	if f+t*O not in B:L[f-1]+=[t-1];L[t-1]+=[f-1]
def dfs(h,R,A):
	q=[[O,h]]
	while q:
		b,h=q.pop()
		if R[h]^1:
			R[h]=1;A[h]=T
			for n in L[h]:
				if b^n:q+=[[h,n]]
T=-1;dfs(0,R,A)
for T in X(Q,0,-1):
	f,t=E[M+T-1];f-=1;t-=1
	L[f]+=[t];L[t]+=[f]
	if R[f]:dfs(t,R,A)
	elif R[t]:dfs(f,R,A)
for i in X(1,N):print A[i]
0