[已解决]同志们，这题应该怎么做啊？想了很久想不通······

小冰冰偶哈哈

小明来到某国，某国总共有n个城市，分别是0~n-1号城市，任意两个城市之间都有一条通道可以来往，每个通道需要一定的时间才能通过。现在小明在0号城市，他希望通过通道到达1号城市。
小明为了更快到达1号城市，买了辆自行车（有骑行次数），使用自行车可以使一条通道花费时间减半，自行车骑行次数是k次，问小明从0号城市到1号城市需要多长时间？
要求：
输入包括n+1行
第一行两个正整数n，k（2<=n<=50  ,   0<=k<=50）分别表示城市数量和自行车使用次数，以空格分割
接下来n行，每行是一个长度为n的字符串time,time[j]（‘0’<=time[j]<='9',）表示从i号城市到j号城市的时间，对所有合法i和j满足time[j]=time[j],对所有合法的i满足time=0
输出一个实数表示小明从0号城市到1号城市的最短时间（Python编写）
样例输入：3 2
                 073
                 703
                 330
输出：3.0

最佳答案

月排行榜 / 总排行榜

jerryxjr1220

2017-9-15 10:39:36

最优路径问题，可以参考
http://bbs.fishc.com/thread-81056-1-1.html

跳转到最佳答案楼层

SuMo

很抱歉,我智商可能太低了..... 没看懂题目到底什么意思..... 能再描述下么

黑猪儿

SuMo 发表于 2017-9-14 15:39
很抱歉,我智商可能太低了..... 没看懂题目到底什么意思..... 能再描述下么

不懂不懂

bush牛

为什么我根据你的样例，得出来的结果应该是3.0。
0 到 1 为 7
0 到 2 为 3
1 到 2 为 3
2次骑车 ，结果为(3+3)/2【路线0-2-1】

小冰冰偶哈哈

黑猪儿 发表于 2017-9-14 16:27
不懂不懂

就是n个城市标号0~n-1，两两个城市通道可以直达（相当于时空隧道），现在在0号城市，想去1号城市，已知各个城市通道的时间，例如，你可以从0号城市直接到1号城市，也可以从0号城市-->3号城市-->4号城市-->1号城市，问多种方法中，哪种方法时间最短，返回最短时间。确实好难！我还没想出来，思想知道，就是写不出程序来，写着写着就懵逼了

新科技网络公司

确实 很难 小白的我看着已经懵逼了、

新手·ing

那两个城市之间有几个通道呢

新手·ing

或者从其他几个城市绕道1号

ttlwjljj

输入：5 1
0 10 7 2 4
10 0 3 8 1
7 3 0 4 5
2 8 4 0 3
4 1 5 3 0
3.0

输入：5 2
0 10 7 2 4
10 0 3 8 1
7 3 0 4 5
2 8 4 0 3
4 1 5 3 0
2.5

输入：5 3
0 10 7 2 4
10 0 3 8 1
7 3 0 4 5
2 8 4 0 3
4 1 5 3 0
2.5

试了一下这个，应该没写错吧，暴力枚举的结果

小冰冰偶哈哈

新手·ing 发表于 2017-9-14 21:56
或者从其他几个城市绕道1号

一个通道

小冰冰偶哈哈

bush牛 发表于 2017-9-14 16:33
为什么我根据你的样例，得出来的结果应该是3.0。
0 到 1 为 7
0 到 2 为 3

是的，我打错了

小冰冰偶哈哈

ttlwjljj 发表于 2017-9-15 00:38
输入：5 1
0 10 7 2 4
10 0 3 8 1

楼主有代码提供吗？我老是写卡隔

jerryxjr1220

最优路径问题，可以参考
http://bbs.fishc.com/thread-81056-1-1.html

chunchun2017

这是考最优路径啊

baicel21314

我是来学习的，呵呵，新手一枚。。

小冰冰偶哈哈

jerryxjr1220 发表于 2017-9-15 10:39
最优路径问题，可以参考
http://bbs.fishc.com/thread-81056-1-1.html

谢谢

小剑剑

小冰冰偶哈哈 发表于 2017-9-15 16:23
谢谢

楼主可以去了解一下dikastra算法

cyndiwants

我也不会，但是顶楼主一下，加油

longlive

已解决了啊，继续加油