1529: 快递的方案数
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：25
Solved：13
Description
快递小哥在一个小区里送货物，小区由 n 个路口组成，路口编号为 1 到 n ，路口之间双向道路。输入的数据保证你可以从任意路口出发可以到达其他任意路口。
给你一个整数 n 和 m条边来描述小区的道路。第 i 条边连接端点 Ai 和 Bi表示通过这一条道路所需要花费的时间Ti 。你想知道花费最少时间从路口 1 出发到达路口 n 的方案数。请返回快递小哥花费最少时间到达目的地的不同路径的方案数 。
如下图共有3条最少时间到达n的方案: (1) 1 → 7 ; (2) 1 → 5 → 7 ; (3) 1 → 2 → 3 →6 → 7 。 输出答案为3 。
给你一个整数 n 和 m条边来描述小区的道路。第 i 条边连接端点 Ai 和 Bi表示通过这一条道路所需要花费的时间Ti 。你想知道花费最少时间从路口 1 出发到达路口 n 的方案数。请返回快递小哥花费最少时间到达目的地的不同路径的方案数 。
如下图共有3条最少时间到达n的方案: (1) 1 → 7 ; (2) 1 → 5 → 7 ; (3) 1 → 2 → 3 →6 → 7 。 输出答案为3 。
Input
输入第一行为两个正整数n m。n表示顶点个数（顶点编号为0~n-1），m表示边的条数。接下来m行，每行有3个数Ai, Bi,及Ti。表示顶点 A到顶点 B所化费的时间值Ti。
Output
输出快递小哥花费最少时间到达目的地的不同路径的方案数 。
Sample Input Copy
7 11
1 2 2
1 5 5
1 7 7
2 3 3
2 4 4
3 4 1
3 6 1
4 6 2
4 7 3
5 7 2
6 7 1
Sample Output Copy
3
HINT
2=<n<=20 ; 0=<g[i][j]<=1000 (没有负数)