desc.md 1.0 KB
Newer Older
每日一练社区's avatar
每日一练社区 已提交
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
## 标题
最短路径数
## 题目描述
现给定一张无向图(节点有权),求从一点出发到另一点的最短路径的条数,以及经过节点的权之和的最大值。

![](https://img-blog.csdn.net/20140219093337421?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvdGlhbnRhbmdyZW5qaWFu/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast)
#### 输入
```
4 5 0 3
1 4 1 2
0 1 1
0 2 2
0 3 4
1 2 1
2 3 2
```
#### 输入解释
第一行:4 5 0 3 表示4个点,总共5条路径,求从0号点到3号点的最短路径的条数及经过节点的权之和和的最大值  
第二行:1 4 1 2 表示0号点的权值为1,1号点的权值为4,2号点的权值为1,3号点的权值为2  

接下来的5行,表示5条路径的长度。  

0号点与1号点之间的路径长度为1  
0号点与2号点之间的路径长度为2  
0号点与3号点之间的路径长度为4  
1号点与2号点之间的路径长度为1  
2号点与3号点之间的路径长度为2  
#### 输出
```
3 8
```