路径统计

Grade 100 Open Time Wednesday, 17 June 2020, 9:05 PM
Discount 0.8 Time Discount Wednesday, 17 June 2020, 9:05 PM
Allow late Yes Close Time Wednesday, 17 June 2020, 9:05 PM
Input file path.in Output file path.out

【题目描述】路径统计(path)

地图上有N个结点和E条道路,所有道路都是单向的,问从结点1到结点N的最短路径有多少条?

【输入格式】

输入第一行为两整数N和E,表示结点和道路数。

随后E行,每行三个数x、y、c,表示从结点x到结点y有道路相连且花费时间为c(可能有重复输入的边,但保证x≠y,1≤x,y≤n)。

【输出格式】

输出两个数,分别是最少花费时间和花费时间最少的路径数。

两个不同的最短路方案要求:路径长度相同(均为最短路长度)且至少有一条边不重合。

若城市N无法到达则输出“No answer”。

【输入样例】

5 5

1 2 1

2 3 1

3 4 1

1 4 3

4 5 2

【输出样例】

5 2

【数据规模】

对于30%的数据:N≤20;

对于100%的数据:1≤N≤2000,0≤E≤N×(N-1),1≤c≤10。