进击的小豪

发布时间: 2017年6月19日 00:24   时间限制: 1000ms   内存限制: 128M

   shuacm的同学都知道小豪是一个热血少年,爱挑战爱拼搏。小豪还有一大爱好,当然是刷题了。对!就是昨天小豪睡好午觉刚准备拿着书包直奔图书馆开刷,却发现自己由于前一天CF打太晚了把自己的笔记本忘在东区机房了。OH!真是太糟糕了,没有办法只能去一趟东区了。学校构成一张有n (1<n<=1000)个结点的无向带权图,小豪所住的校内5号楼在1号结点,东区机房在2号结点。小豪有一个特殊的癖好,他只会走(a->b)满足存在一条从b出发去东区的路,比所有从a出发去东区的路都短。现在告诉你小豪走每条路所需要的时间,你能不能帮助小豪找到一共有几条路径从寝室到东区呢?(聪明的小豪会从中挑选的^.^)

输入数据有多组,每组数据的第一行包含两个整数n(1<n<=1000), 0<m<5000。接下来有m行每行三个数 a, b,(1<=a,b<=n) c(1<=c<=1000000)分别表示a与b之间有一条路径小豪走这条路需花费c单位的时间,当n=0表示输入结束。

输出数据占一行包含一个整数,表示有多少种路径。(保证输出小于2^31-1)

复制
2 1
1 2 1
0
1
1719

old_judge

old_judge_None