| 题目名称 | 1592. [SGU U236]贪心路径 |
|---|---|
| 输入输出 | greedypath.in/out |
| 难度等级 | ★★ |
| 时间限制 | 250 ms (0.25 s) |
| 内存限制 | 4 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cstdio
于2014-04-14加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：6， 提交：18， 通过率：33.33% | ||||
 Chenyao2333 |
100 | 0.005 s | 0.37 MiB | C++ |
 ww944606393 |
100 | 0.005 s | 0.37 MiB | C++ |
 HouJikan |
100 | 0.008 s | 0.31 MiB | C++ |
 mikumikumi |
100 | 0.009 s | 0.40 MiB | C++ |
 cstdio |
100 | 0.013 s | 0.40 MiB | C++ |
 doriko |
100 | 0.036 s | 0.13 MiB | Pascal |
|
Chenyao2333 |
90 | 0.007 s | 0.37 MiB | C++ |
 abaoo |
90 | 0.025 s | 0.40 MiB | C++ |
|
HouJikan |
60 | 0.005 s | 0.31 MiB | C++ |
|
HouJikan |
20 | 0.004 s | 0.31 MiB | C++ |
| 关于 贪心路径 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
精度问题作死OTZZZZZZZZZZZZZZZZZZZZZZZZZZ
| ||||
|
回复 @Chenyao :
看输出格式…… | ||||
|
@cstdio 数据第四个点输出的是0,不是0.00
 | ||||
【题目描述】
有n个城市，被m条路连接着。最近成立了一些旅行社，在这些城市之间给旅行者们提供服务。旅行者从城市i到城市j需要付给旅行社的费用是Ci,j，需要的时间为Ti,j 。很多旅行者希望加入旅行社，但是旅行社只有一辆车。于是旅行社的老板决定组织一次旅行大赚一笔。公司里的专家需要提供一条使得贪心函数F(G)最大的回路G。F(G) 等于总花费除以总时间。但是没有人找到这样的回路，于是公司的领导请你帮忙。
【输入格式】
第一行包含两个数n(3≤n≤50),m 分别表示点数和边数。
接下来m行每行包含一条路的描述。输入四个数,A,B,C[A,B],T[A,B]（0≤C[A,B]≤100，0≤T[A,B]≤100）
【输出格式】
如果不存在这样的回路，输出0.
否则输出回路的贪心函数，保留两位小数。
【样例输入】
4 5
1 2 5 1
2 3 3 5
3 4 1 1
4 1 5 2
2 4 1 10
【样例输出】
1.56
【提示】
选取回路1->2->3->4->1。
这里的输出格式和SGU上原题有所不同。
【来源】
Author:Sergey Simonchik