#P1608. P1608 路径统计

P1608 路径统计

P1608 路径统计

普及+/提高 | 来源:洛谷 | 原题链接

题意

给定 nn 个点、EE 条有向边(花费 CC,1≤C≤101\le C\le 10,边信息可能重复,保证 IeJI e J)。求 1→n1\to n 的最少花费与最短路条数。两条路径不同当且仅当经过的点编号序列不同——所以重复的同向同权边不增加计数。无法到达只输出 No answer。路径数不超过 2302^{30},不取模。

输入格式

输入文件第一行为两个空格隔开的数 N,EN, E,表示这张地图里有多少个小镇及有多少边的信息。

下面 EE 行,每行三个数 I,J,CI, J, C,表示从 II 小镇到 JJ 小镇有道路相连且花费为 CC。(注意,数据提供的边信息可能会重复,不过保证 IeJI e J,1≤I,J≤N1 \leq I, J\leq N)。

输出格式

输出文件包含两个数,分别是最少花费和花费最少的路径的总数。保证花费最少的路径的总数不超过 2302^{30}。

两个不同的最短路方案要求:路径长度相同(均为最短路长度)且最短路经过的点的编号序列不同。

若城市 NN 无法到达则只输出一个 No answer。

输入输出样例

样例 1 输入

5 4
1 5 4
1 2 2
2 5 2
4 1 1

样例 1 输出

4 2

数据范围

1≤N≤20001\le N\le 2000,0≤E≤N×(N−1)0\le E\le N\times(N-1),1≤C≤101\le C\le 10;路径总数不超过 2302^{30}(不取模)。

提示

考点:Dijkstra + 最短路 DAG 上计数。易错点:① 重边按方向去重、同方向取最小权(点序列不同才算不同路径,重复边既不改变最短路也不增加计数;但不同权重的重复边只保留最小的,否则最短路会算错);② 计数时条件是 dist[u]+w=dist[v]dist[u]+w=dist[v] 且 C≥1C\ge1 保证无环;③ NN 无法到达输出 No answer;④ 与 P1144 对比:本题权值≥1 不能用 BFS,且不取模。

四、综合应用

蜀ICP备2025119001号-1