首页 > 试题广场 >

如图所示, 图中每条边上的数字表示该边的长度,则从 A

[填空题]
如图所示,
图中每条边上的数字表示该边的长度,则从 A 到 E 的最短距离是1

查看答案及解析
添加回答
LiuCow2022头像 LiuCow2022
这个图就歪倒离谱，绕一个圈都比直线要路程短
直线a——————》f 长度：6
圈a————》b————》c————》f 长度：5
就nm离谱

发表于 2022-08-23 20:53:40 回复(0)
牛客39225859号头像 牛客39225859号
我们可以用倒推的方法，求A到E的最短距离。用k来表示阶段。
第一步：k=4 有 d4（F，E）来表示F到E的距离，4表示第四阶段。
f4(F)=6

第二步：k=3 有四条路到F，用d3（C，E）、d3（C，F）、d3（D，F）、d3（D，E）来表示这四条路，3表示第三阶段。
f3(C)=min{d3（C，E）、d3（C，F）}
=min{8，1+6}=7
f3(D)=min{d3（D，F）、d3（D，E）}
 =min{2+6,4}=4
第三步：k=2 有
f2(B)=min{d2(B,C),d2(B,D)}
=min{1+7,7+4}=8
f2(G)=min{d2(G,C),d2(G,D)}
=min{2+7,4+4}=8
第四步：k=1有
f1(A)=min{d1(A,B),d1(A,G),d1(A,F)}
=min{3+8,4+8,6+6}=11
答案：11 。
发表于 2020-08-29 21:38:35 回复(2)
提交观点

问题信息

普及 C++ 图论 Pascal 问题求解
来自：NOIP2014初赛普及组
上传者：牛客309901号
难度：
2条回答 3386浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号