P3001 [USACO10DEC]巨无霸Big Macs Around the w…

    • 35通过
    • 171提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 USACO 2010 Special Judge
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    Bessie正在学习她最喜欢的科目宏观经济学,作为她最后一门学科,她将对世界各种货币的汇率进行研究。

    题目描述

    Bessie is studying her favorite subject, Macroeconomics, in cowllege. For her final project, she will be presenting research on exchange rates between countries around the world.

    In order to make her presentation more lively, she would like to show the relative prices of Big Macs around the world, despite their rather unsavory contents. To illustrate, suppose that Bessie would like to find smallest value of a Big Mac in a country given its value in some initial country and exchange rates from which other country's values can be calculated (as illustrated below):

    * A Big Mac is worth 60 dollars in the United States 
    * The exchange rate from US dollars to Canadian dollars is 0.2 Canadian dollars per US dollar 
    * The exchange rate from US dollars to British Pounds is 5.00 British Pounds per US Dollar 
    * The exchange rate from British Pounds to Canadian dollars is 0.5 Canadian dollars per British Pound 
    * The exchange rate between Canadian dollars to US dollars is 5.00 US dollars per Canadian dollar and Bessie would like to find the smallest possible value of a Big Mac in Canada that can be obtained by exchanging currencies. There are two ways: 
    * Going from US dollars directly to Canada dollars would yield a burger worth 60.00 US dollars * 0.2 Canadian dollars / US dollar = 12.00 Canadian dollars 
    * Going from US dollars to British Pounds to Canadian dollars would yield a burger worth 60.00 US$ * 5.00 GBP / 1 US$ * 0.5 C$ / 1 GBP = 150.00 C$ (Canadian dollars). 
    Bessie would choose the former option, since she would much rather pay 12.00 Canadian dollars instead of 150.00 Canadian dollars for a Big Mac in Canada. 
    Bessie has N (1 <= N <= 2,000) countries conveniently labeled 1 to N that she would like to consider along with a list of M (1 <= M <= 25,000) exchange rates e_ij (0.1 < e_ij <= 10), each between countries i and j (1 <= i <= N; 1 <= j <= N). 
    Given the value V (1 <= V <= 1,000,000,000,000), which is not 
    necessarily an integer, of the Big Mac in her starting country A (1 <= A <= N), help her find the smallest possible value of a Big Mac in country B (1 <= B <= N; B != A) after a series of currency conversions. If there is no minimum, output 0. 

    It is guaranteed that the answer is, if not 0, between 1 and 10^15. It is also guaranteed that, for any country's currency, it is

    possible to get to any other country's currency.

    为了让她的演讲更加生动,她会展示一个叫做“BM”的商品在全世界的相对价格。举个例子,Bessie会通过其他国家的汇率去找到一件BM在一个国家的最小价值(如下所示)

    一件BM在美国值60美元;

    美元与加拿大元的汇率为一美元换0.2加拿大元(1:0.2)

    美元与英镑的汇率为一美元换五英镑(1:5)

    英镑与加拿大元的汇率为一英镑换0.5加拿大元(1:0.5)

    加拿大元与美元的汇率是五美元换一加拿大元(5:1[通过上面的可以换算得出]),Bessis有两种方法通过货币兑换在加拿大这个国家找到一件BM的最低价值:

    一:拿着美元直接去加拿大,通过汇率得出一件BM只要十二加拿大元

    二:拿着美元去英国,兑换为英镑后再去加拿大,得出一件BM要一百五十加拿大元

    (由于长度,剩下…

    输入输出格式

    输入格式:

    (续)

    Bessie会选择前一种方案因为她更乐意为在加拿大买一件BM支付十二加元而不是一百五十加元。

    Bessie有N(1<=N<=2000)个国家的信息和M种汇率(1<=M<=25000),在i,j国间的汇率表示为e_ij(0.1<=e_ij<=10)。

    给你一个值V(1<=V<=1000000000000),但V不一定是一个整数。V是BM在Bessie起始国家A的价格,帮助她寻找到在B国BM最低的价格,如果不存在,则输出0。

    数据保证答案小于十的十五次方,也保证所有国家都可以通过汇率将钱币转为别的国家的。

    * Line 1: Five space-separated numbers: N, M, V, A, B

    * Lines 2..M+1: Three space-separated numbers: i, j, e_ij

    第一行:五个数:N,M,V,A,B 分别一个空格隔开

    第2到M+1行:三个数i,j,e_ij 分别一个空格隔开

    输出格式:

    * Line 1: A single positive number, the price of the Big Mac, with absolute or relative error at most 10^-6. If there is no minimum, output 0.

    一行:BM在B国的最低价格,精确到10^-6。如果没有最小值,输出0

    输入输出样例

    输入样例#1: 复制
    3 4 60 1 2 
    1 2 0.2 
    1 3 5 
    3 2 0.5 
    2 1 5 
    
    输出样例#1: 复制
    12.00 
    

    说明

    注意 这里的汇率是单向的

    感谢@JJYZ_cbh 的耐心翻译

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。