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

【 問(wèn)題描述 】

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

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

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

例子

?????? 下圖給出了一個(gè)網(wǎng)絡(luò)，每條路有兩個(gè)參數(shù)：費(fèi)用和時(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)。

?

問(wèn)　題 ：

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

?

【 輸入文件 】 ：

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

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

【 輸出文件 】 ：

?????? 僅一個(gè)數(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	該例對(duì)應(yīng)前面的圖。