# @param {Integer} n # @param {Integer[][]} red_edges # @param {Integer[][]} blue_edges # @return {Integer[]} def shortest_alternating_paths(n, red_edges, blue_edges) adjred=n.times.map{[]} adjblu=n.times.map{[]} red_edges.each{|i,j|adjred[i]<<j} blue_edges.each{|i,j|adjblu[i]<<j} vis=[nil]*(2*n) q=[] l=r=0   q[r]=[0,0,0];r+=1 q[r]=[0,1,0];r+=1 while l<r a,c,t=q[l];l+=1 next if vis[a*2+c] vis[a*2+c]=t if c==0 adjblu[a].each do|v| q[r]=[v,1,t+1];r+=1 end else adjred[a].each do|v| q[r]=[v,0,t+1];r+=1 end end end t=[10**18]*n (0...n).each do|i| t[i]=[t[i],vis[i*2]||10**18].min t[i]=[t[i],vis[i*2+1]||10**18].min t[i]=-1 if t[i]==10**18 end t end그냥 BFS