Problem : 139 - 海綿寶寶之海之霸(最短路負權)

Problem Statistics

Solved Member: 40　　Submission: 524　　User Tried: 51

Statement:

這是皮老闆。

今天派大星又想吃美味蟹堡了！
最近蟹堡王業績太好，引來對面海之霸的皮老闆的「高度」關注。
現在皮老闆在比奇堡的道路上面倒了很多廢油，讓某些道路的長度變成負的〈因為很滑，根本不需要動腳〉。
不巧，派大星剛好需要這樣的協助，於是他要抵達蟹堡王需要走過的道路長度變短了！
現在，比奇堡一樣有n個節點，和m條連接n個節點的單向道路，但是道路長度有可能是負的。
請你告訴派大星，他現在從節點1到位於節點n的蟹堡王所需要走的最短路徑是多少吧！
如果不存在這樣的最短路徑，或是他需要走過的最短路徑無限小，請輸出"QAQ"。

Input:Output:

第一行有兩個數字n, m。(n ≦ 500, m ≦ 20000)
接下來有m行，每一行有三個數字a, b, c (1 ≦ a,b ≦ n, -10000 ≦ c ≦10000)，代表從節點a到節點b有一條長度為c的單向道路連接。

輸出一個數字，代表派大星要到蟹堡王的最短路徑。
若不存在最短路徑或是最短路徑長度無限小，請輸出"QAQ"(不含引號)。

Sample Input:Sample Output:

3 3
1 2 -1
2 1 -1
1 3 2

QAQ

HINT:

珊迪表示：「答案可能是負的。」
我愛海綿寶寶>///<

新增一筆測試資料10c @ 2013/10/14 18:24 by hanhan0912

Problem Setter

bigelephant29

Testdata:

Test	Time	Memory	Score
0	1000ms	65536kb
1-1	1000ms	65536kb	10
1-2	1000ms	65536kb
2-1	1000ms	65536kb	10
2-2	1000ms	65536kb
3-1	1000ms	65536kb	10
3-2	1000ms	65536kb
4-1	1000ms	65536kb	10
4-2	1000ms	65536kb
5-1	1000ms	65536kb	10
5-2	1000ms	65536kb
6-1	1000ms	65536kb	10
6-2	1000ms	65536kb
7-1	1000ms	65536kb	10
7-2	1000ms	65536kb
8-1	1000ms	65536kb	10
8-2	1000ms	65536kb
9-1	1000ms	65536kb	10
9-2	1000ms	65536kb
10-1	1000ms	65536kb	10
10-2	1000ms	65536kb
10-3	1000ms	65536kb