網址

http://poj.org/problem?id=3169

題意

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

例：

全部的牛都在同一點 -> 合法 牛1與牛2在同一點 -> 合法
牛1與牛3在同一點，而牛2在牛3之後 -> 不合法，牛2與牛3的順序沒按照編號。

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

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

Technique details

-  牛隻數量 **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，此時即可列出式子 xB - xA ≤ D。若 A 牛與 B 牛互相討厭，且需要距離大於等於 D，則可列出式子 xB - xA ≥ D。

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

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