題目：http://poj.org/problem?id=3767
有n個點m條邊的無向帶權圖(2<=N<=600，0<=M<=10000)
形容的說法是每個點不是屬於國家1、就是屬於國家2
Mr.M現在會從一個屬於國家1的點出發，問走到某個國家2點的最短路是多少？
但是不同國家間的交通必須繳交通行證，不巧Mr.M只申請了一張
程式碼：http://codepad.org/Ml5A8VNL
(code有點久遠了...風格不太一樣)
關鍵就在構圖
同屬國家1的點之間，可以自由通行、國家2同理
但是國1到國2的邊只能走1次
因為走到國2就不能走回來了，不妨設定該邊是單向國1->國2的邊
然後直接作最短路，平安結束
沒有留言:
張貼留言