題解：ABC277E - Crystal Switches

·題目

鏈接：Atcoder。

鏈接：洛谷。

·難度

算法難度：B。

思維難度：A。

調碼難度：C。

綜合評價：普及+/提高。

·算法

寬度優先搜索+拆點思路

·思路

把每個點分為兩段，分別是連接著取值為0的邊的（A份）和權值為1的邊的（B份）。如果一條邊權值為0，就把兩個點的A份相連，否則把B份相連，如果一個點上有按鈕，就把它A份里連接的點和B份連接，B份里連接的點和A份連接，最后按照普通bfs做就能夠得出正確答案。

·代價

O(n+m)，每個點和每條邊分別被遍歷到一次。

·細節

拆點用+n來實現。

·代碼

AC。

·注意

輸出-1要特殊判斷。