首页 > 试题广场 >

龟兔赛跑

[编程题]龟兔赛跑
  • 热度指数：1286 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 90M，其他语言180M
  • 算法知识视频讲解
定义如下图所示的比赛地图：
 
S表示比赛起点，E表示比赛终点。实线表示陆路，虚线表示水路。兔子只能走陆路，乌龟既可以走陆路也可以走水路。每条路径的长度在图中给出。假定兔子和乌龟足够聪明，问谁先到达终点。

输入描述:
第1行输入v1，v2。v1是兔子的速度，v2是乌龟的速度（水路、陆路速度相同）。第2行输入n,m，点的编号是1~n,然后是m行，其中1是起点，n是终点（路径本身不限定方向）。下面m行4个数 a, b, d, c，表示a和b之间有一条边，且其长度为d，类型是c（0表示陆路，1表示水路）。最后一行是end，表示输入结束。输入保证1和n之间至少有一条路径联通。(1<n<=10000, 0<m<=1000000)。


输出描述:
输出-1,0,1中的一个数。-1表示乌龟获胜，1表示兔子获胜，0表示同时到达终点。
示例1

输入

10 5
3 3 
1 2 30 0
2 3 20 0
1 3 20 1
end

输出

-1
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 图 PHP工程师 小米集团 搜狗 2019 Java工程师
来自：搜狗2019秋招研究员...
上传者：小小
难度：
0条回答 5637浏览

热门推荐

通过挑战的用户

查看代码

相关试题

龟兔赛跑

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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