提出 #62153446

---

ソースコード 拡げる

N,M,S,T = gets.split.map(&:to_i)
E = Array.new(N+1){[]}
M.times{
	u,v = gets.split.map(&:to_i)
	E[u]<<v
	E[v]<<u
}
S2 = lambda{ # S からの距離一覧。T 以降はなし
	ds = [nil]*(N+1)
	ds[S] = 0
	*q = S
	while s = q.shift
		E[s].each{|t|
			if ! ds[t]
				ds[t] = ds[s]+1
				q<<t
			end
		} if s!=T
	end
	next ds
}.call
#warn :ST,[S,T].inspect
#warn :S2,S2.inspect

SP = [T] # S から T への最短パス(の１つ)
until SP[-1]==S
	t = SP[-1]
	d = S2[t]-1
	SP<<E[t].find{|s| S2[s]==d }
end
SP.reverse!
SP？ = SP.each_with_index.to_h
#warn :SP,SP.inspect

AP = [0]*N # S から T への代替パスの数(添字は増分)
SP[1..].each{|t|
	d0 = S2[t]-1
	E[t].each{|s|
		if ! SP？[s]
			d2 = S2[s]
			AP[d2-d0] += 1 if d2
		end
	}
}
APD = AP.index{0<_1} # 最善の代替パスの最短からの増分
#warn :AP,AP.inspect
#warn :S2T,S2[T]
#warn :APD,APD

S2Y = lambda{ # S から待避場所(Y字分岐路)までの距離
	s = S
	while s
		d = S2[s]+1
		s,t2 = E[s].select{|t| ! SP？[t] && S2[t]==d }
		break if t2
	end
	next d if s
}.call
#warn :S2Y,S2Y

T2Y = lambda{ # T から待避場所(Y字分岐路)までの距離
	s = T
	while s
		d = S2[s]+1
		s,t2 = E[s].select{|t| ! S2[t] && S2[t] = d }
		break if t2
	end
	next d-S2[T] if s
}.call
#warn :T2Y,T2Y

p([
	(2*S2[T]+APD if APD),
	(2*S2[T]+4*S2Y if S2Y),
	(2*S2[T]+4*T2Y if T2Y)
].tap{
#warn _1.inspect
#warn %w[代替パス Sから待避 Tから待避][_1.index _1.compact.min]
}.compact.min||-1)

提出情報

ジャッジ結果