#P1608. P1608 路径统计
P1608 路径统计
P1608 路径统计
普及+/提高 | 来源:洛谷 | 原题链接
题意
给定 个点、 条有向边(花费 ,,边信息可能重复,保证 )。求 的最少花费与最短路条数。两条路径不同当且仅当经过的点编号序列不同——所以重复的同向同权边不增加计数。无法到达只输出 No answer。路径数不超过 ,不取模。
输入格式
输入文件第一行为两个空格隔开的数 ,表示这张地图里有多少个小镇及有多少边的信息。
下面 行,每行三个数 ,表示从 小镇到 小镇有道路相连且花费为 。(注意,数据提供的边信息可能会重复,不过保证 ,)。
输出格式
输出文件包含两个数,分别是最少花费和花费最少的路径的总数。保证花费最少的路径的总数不超过 。
两个不同的最短路方案要求:路径长度相同(均为最短路长度)且最短路经过的点的编号序列不同。
若城市 无法到达则只输出一个 No answer。
输入输出样例
样例 1 输入
5 4
1 5 4
1 2 2
2 5 2
4 1 1
样例 1 输出
4 2
数据范围
,,;路径总数不超过 (不取模)。
提示
考点:Dijkstra + 最短路 DAG 上计数。易错点:① 重边按方向去重、同方向取最小权(点序列不同才算不同路径,重复边既不改变最短路也不增加计数;但不同权重的重复边只保留最小的,否则最短路会算错);② 计数时条件是 且 保证无环;③ 无法到达输出 No answer;④ 与 P1144 对比:本题权值≥1 不能用 BFS,且不取模。