เส้นทางที่สั้นที่สุดพร้อมการสลับสีใน Python

สมมติว่าเราได้กำหนดทิศทางของกราฟ โดยมีโหนดชื่อ 0, 1, ..., n-1 ในกราฟนี้ ขอบแต่ละด้านจะมีสีแดงหรือสีน้ำเงิน และอาจมีขอบในตัวเองหรือขอบขนานกัน แต่ละ [i, j] ใน red_edges ระบุถึงขอบสีแดงจากโหนด i ไปยังโหนด j ในทำนองเดียวกัน [i, j] แต่ละรายการใน blue_edges จะระบุถึงขอบสีน้ำเงินที่กำกับจากโหนด i ไปยังโหนด j เราต้องหาคำตอบอาร์เรย์ของความยาว n โดยที่แต่ละคำตอบ[X] คือความยาวของเส้นทางที่สั้นที่สุดจากโหนด 0 ถึงโหนด X เพื่อให้ขอบสีสลับกันไปตามเส้นทาง (หรือ -1 หากเส้นทางดังกล่าวไม่ มีอยู่)

ดังนั้น หากอินพุตเป็น n =3, red_edges =[[0,1],[1,2]] และ blue_edges =[] ผลลัพธ์จะเป็น [0, 1, -1]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดวิธีการที่เรียกว่า bfs() ซึ่งจะใช้เวลา re, be, f และ n

• กำหนดชุดที่เรียกว่าเยี่ยมชม, กำหนดคิวและแทรกแฝด [0, f, 0]

• ในขณะที่ q ไม่ว่างเปล่า

  • ตั้งค่ากระแสไฟสามเท่า สี ขั้นตอนเป็น q[0] และลบออกจาก q

  • สี :=เสริมค่าของสี (จริงเป็นเท็จและในทางกลับกัน)

  • res[current] :=นาทีของ res[ปัจจุบัน] และขั้นตอน

  • ถ้าสีไม่เป็นศูนย์แล้ว

    • สำหรับแต่ละ i [ปัจจุบัน]

      • หากคู่ (i, สี) ไม่ได้เข้าชม ให้แทรก (i, สี) เข้าที่เยี่ยมชมแล้วแทรก [i, สี, ขั้นตอน + 1] ลงใน q

  • มิฉะนั้นเมื่อสีเป็น 0 แล้ว

    • สำหรับแต่ละฉันเป็น[ปัจจุบัน]

      • หากคู่ (i, สี) ไม่ได้เข้าชม ให้แทรก (i, สี) เข้าที่เยี่ยมชมแล้วแทรก [i, สี, ขั้นตอน + 1] ลงใน q

• ในวิธีการหลัก −

• res :=อาร์เรย์ของค่าอินฟินิตี้และขนาดของมันคือ n

• re และ be :=อาร์เรย์ของ n อาร์เรย์ว่าง

• สำหรับแต่ละองค์ประกอบ i ใน r:แทรก i[1] ลงใน re[i[0]]

• สำหรับแต่ละองค์ประกอบ i ใน b:แทรก i[1] ลงใน be[i[0]]

• โทร bfs(re, be, false, n) และ call bfs(re, be, true, n)

• สำหรับฉันในช่วง 0 ถึงความยาวของความละเอียด – 1

  • ถ้า res[i] =inf แล้ว res[i] :=-1

• ผลตอบแทน

ตัวอย่าง(Python)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

คลาส Solution(object):def shortestAlternatingPaths(self, n, r, b):self.res =[float("inf")] * n re =[[] for i in range(n) ] be =[[] สำหรับฉันในช่วง (n) ] สำหรับฉันใน r:re[i[0]].append(i[1]) สำหรับฉันใน b:be[i[0]].append(i[1] ) self.bfs(re,be,False,n) self.bfs(re,be,True,n) for i in range(len(self.res)):if self.res[i] ==float(' inf'):self.res[i]=-1 กลับ self.res def bfs(self,re,be,f,n):เยี่ยมชม =set() คิว =[[0,f,0]] ในขณะที่คิว:ปัจจุบัน, สี, ขั้นตอน =คิว[0] Que.pop(0) สี =ไม่ใช่สี self.res[ปัจจุบัน] =นาที (ตัวเอง.res [ปัจจุบัน], ขั้นตอน) ถ้าสี:สำหรับฉันอีกครั้ง [ปัจจุบัน]:ถ้า (i,color) ไม่ได้เยี่ยมชม:visit.add((i,color)) queue.append([i,color,step+1]) elif not color:สำหรับฉันใน be[current]:if (i,color ) ไม่ได้เยี่ยมชม:visit.add((i,col หรือ)) queue.append([i,color,step+1])ob =Solution()print(ob.shortestAlternatingPaths(3, [[0,1], [1,2]], [])) 
อินพุต
 
3[[0,1],[1,2]][]
 
ผลลัพธ์
 
[0,1,-1]