Submission #62154569

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

D2Y = lambda{|s|
	ds = [nil]*(N+1)
	ds[s] = 0
	while s
		d = ds[s]+1
		s,t2 = E[s].select{|t| ! SP？[t] && ! ds[t] && ds[t] = d }
		break if t2
	end
	next d if s
}
S2Y = D2Y[S] # S から待避場所(Y字分岐路)までの距離
T2Y = D2Y[T] # T から待避場所(Y字分岐路)までの距離
#warn :S2Y,S2Y
#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)

Submission Info

Judge Result