題目描述 Description
某陳和某Y 最近對一個游戲著迷.那是Electronic Arts 今年發布的優秀的模擬經營類游戲,Spore. 在Spore 中,玩家將經歷從單細胞生物到星系的統治者的進化過程,創造並守護你自己的文明. 而某陳在經歷了幾天*幾十分鐘/天的游戲後,也終於已經近乎通關了. 目前,某陳統治著銀河系中標號1 到N 的星系,而他的帝國中心,在星系1 的某顆美麗的行星之上.如同所有銀河系中的文 明一樣,貿易,發展,結盟,擴張,抵抗Grox[銀河系中心的龐大的強悍的恐怖的邪惡帝國]的侵略. 某陳有足夠的力量,他的疆域蔓延幾百個光年.可是Grox 異常強大,他們的飛船出現在某陳了解的任何地方,並時常攻擊任 何位置的某陳和盟友的單位[飛船,建築,星球,甚至星系].戰爭在所難免. 某陳將從帝國中心去標號為N 的星系,他疆域的邊緣,去尋找一個可能存在的通向銀河系中心的黑洞.他要計劃一條合適的 路線. 從星系g1 到達g2,某陳需要花費c1 的代價[主要是燃料,另外還有與沿途Grox 的勢力作戰的花費],c1 小於0 則是因為 這樣的星系旅行,會給某陳帶來收益[來源於物流差價,以及一些殖民地的稅收..].相應地,c2 則是代表從星系g2 到達g1 的代價.據某陳了解,共有M 條這樣的星系間路徑. 為了戰備,他需要選擇一條總代價最小的路線.
輸入描述 Input Description
輸入文件包括多組數據. 對於每一組數據,第一行有2 個整數n,m,如題目描述中的含義,1<=n<=1000,0<=m<=10000. 接下來的m 行,每行會有四個整數g1,g2,c1,c2,如題目描述中的含義.0<=g1,g2<=n.輸入數據保證所有整數都在[- 10000..10000]的范圍內. n=0,m=0 標識著輸入數據的結束.每個輸入文件包含不超過10 組數據.
輸出描述 Output Description
對於每組輸入數據,輸出一行,為從星系1 到星系N 的最小代價的路線的代價. 如果這樣的路線不存在,輸出’No such path’.
樣例輸入 Sample Input
3 2 1 2 2 -1 2 3 0 1 0 0
樣例輸出 Sample Output
2
數據范圍及提示 Data Size & Hint
jiantimu
http://blog.csdn.net/loi_skyline/article/details/52719126
