題目網址：3169 - Layout

題目概述

Farmer John 有 N 頭牛，這些牛站在一條直線上。這些牛皆有被編號（1 ~ N），他們會依照他們的編號順序排列。牛隻可以重疊，但能需要按照順序。

例：

• 全部的牛都在同一點 ⇒ 合法
• 牛₁與牛₂在同一點 ⇒ 合法
• 牛₁與牛₃在同一點，而牛₂在牛₃之後 ⇒ 不合法，牛₂與牛₃的順序沒按照編號。

這些牛就像人一樣，會有喜歡與討厭的情感。若兩頭牛互相喜歡，那麼他們排隊時，距離彼此必須小於等於給定的單位。若他們討厭彼此，則需要距離彼此大於等於給定的單位。要求求出這些牛排隊時最大的長度。

P.S. 牛與牛之間，喜歡與討厭都是雙向的！

Technique Detail

• 牛隻數量 N，2 ≤ N ≤ 1,000
• 喜歡的牛隻對數 ML，1 ≤ ML ≤ 10,000
• 討厭的牛隻對數 MD，1 ≤ MD ≤ 10,000
• 距離 D，1 ≤ D ≤ 1,000,000

輸入格式

測試資料由三個整數開始 N ML MD，表示有 N 頭牛。接下來有 ML 行，每一行三個整數 A B D，表示 A 牛與 B 牛彼此喜歡，他們的距離要小於等於 D。接著再 MD 行，每一行三個整數 A B D，表示 A 牛與 B 牛彼此討厭，他們的距離要小於等於 D。

輸出格式

對於每一筆測試資料，輸出一個整數，最大的排隊長度。若不存在解時，輸出 -1。若存在無限多解時，輸出 -2。

---

解題思路

標準的差分約束題型，若 A 牛與 B 牛互相喜歡，因此他們的距離需要小於等於 D，此時即可列出式子 x_B - x_A ≤ D。若 A 牛與 B 牛互相討厭，且需要距離大於等於 D，則可列出式子 x_B - x_A ≥ D。

在列完式子後，即可利用 Bellman-Ford 來求最短路徑。編號 1 的牛與編號 N 的牛的距離差即為答案。若出現負環，表示無解，輸出 -1。若到達編號 N 的牛的距離為無限大（即無法抵達），表示有任意解，輸出 -2。

Time Complexity: O(N × (ML + MD))

Source Code

Source code on gist.