雙調(diào)路徑 ? bic .pas/c/cpp 　　　　 時間限制：? 3S 　 ??????????? ? ??? 100 分 ???????? ??????? ????????????????????

【 問題描述 】

如今的道路收費發(fā)展很快。道路的密度越來越大，因此選擇最佳路徑是很現(xiàn)實的問題。城市的道路是雙向的。每條道路有固定的旅行時間以及需要支付的費用。

?????? 路徑是連續(xù)經(jīng)過的道路組成的。總時間是各條道路旅行時間的和，總費用是各條道路所支付費用的總和。一條路徑越快，或者費用越低，該路徑就越好。嚴格地說，如果一條路徑比別的路徑更快，而且不需要支付更多費用，它就比較好。反過來也如此理解。如果沒有一條路徑比某路徑更好，則該路徑被稱為最小路徑。

?????? 這樣的最小的路徑有可能不止一條，或者根本不存在路徑。

例子

?????? 下圖給出了一個網(wǎng)絡，每條路有兩個參數(shù)：費用和時間。

?

?????? 從1到4有4條路徑。1?2?4?(fee?4, time?5), 1?3?4?(fee?4, time?5), 1?2?3?4?(fee?6, time?4)，1?3?2?4?(fee?4, time?10)。

????? 1?3?4 和 1?2?4比 1?3?2?4更好。有兩種最佳路徑：fee?4, time?5 (roots 1?2?4 and 1?3?4) 和 fee?6, time?4 (root 1?2?3?4)。

?

問　題 ：

????? 從文件bic.in中讀入網(wǎng)絡，計算最小路徑的總數(shù)。費用時間都相同的兩條最小路徑只算作一條。你只要輸出不同種類的最小路徑數(shù)即可。

?

【 輸入文件 】 ：

????? 文件的第一行有4個整數(shù)，城市總數(shù)n, 1? ￡ ?n? ￡ ?100, 道路總數(shù) m, 0? ￡ ?m? ￡ ?300, 起點和終點城市s，e, 1? ￡ ?s,?e? ￡ ?n, s? 1 ?e 。接下來的m行每行描述了一條道路的信息，包括4個整數(shù)，兩個端點p，r，費用c，以及時間t，1? ￡ ?p,?r? ￡ ?n, p? 1 ?r, 0? ￡ ?c? ￡ ?100, 0? ￡ ?t? ￡ ?100 。

????? 兩個城市之間可能有多條路徑連接。

【 輸出文件 】 ：

?????? 僅一個數(shù)，表示最小路徑的總數(shù)。

【 樣　 例 】

Bic.in	bic.out	Comments
4 5 1 4 2 1 2 1 3 4 3 1 2 3 1 2 3 1 1 4 2 4 2 4	2	該例對應前面的圖。