We will find a way, we always have.

-interstellar

Problem Solving/๋ฐฑ์ค€

[๋ฐฑ์ค€] 5942๋ฒˆ: Big Macs Around the World

Redddy 2023. 9. 18. 00:02

๐Ÿ”ˆ ๋ฌธ์ œ

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 StatesThe exchange rate from US dollars to Canadian dollars is 0.2 Canadian dollars per US dollarThe exchange rate from US dollars to British Pounds is 5.00 British Pounds per US DollarThe exchange rate from British Pounds to Canadian dollars is 0.5 Canadian dollars per British PoundThe 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 dollarsGoing 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.

 

๐Ÿ“์ž…๋ ฅ

Line 1: Five space-separated numbers: N, M, V, A, B
Lines 2..M+1: Three space-separated numbers: 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.

 

๐Ÿ“š ๋ฌธ์ œ ํ’€์ด

 

๊ฐ ๋‚˜๋ผ๋ฅผ ๋…ธ๋“œ๋ผ๊ณ  ์ƒ๊ฐํ•˜๊ณ , ๋‚˜๋ผ๋งˆ๋‹ค ํ™˜์œจ์€ ๊ฐ ๋…ธ๋“œ๋ฅผ ์ด์–ด์ฃผ๋Š” ๊ฐ„์„ ์ด๋ผ๊ณ  ์ƒ๊ฐํ•œ๋‹ค. A ์—์„œ B๋กœ ์ด๋™ํ•  ๋•Œ ๊ฐ„์„ ์˜ ๊ฐ€์ค‘์น˜๋ฅผ ๊ณฑํ•˜๋ฉฐ ์ด๋™ํ•œ๋‹ค. 

 

๊ทธ๋Ÿฌ๋ฉด ์ตœ๋‹จ๊ฒฝ๋กœ ๊ทธ๋ž˜ํ”„ ๋ฌธ์ œ๋กœ ๋ณ€๊ฒฝ๋˜๋Š”๋ฐ, ์ด๋•Œ ์Œ์ˆ˜ ์‚ฌ์ดํด์ด ๋ฐœ์ƒํ•  ์ˆ˜ ์žˆ์œผ๋‹ˆ ๋‹ค์ต์ŠคํŠธ๋ผ๊ฐ€ ์•„๋‹Œ ๋ฒจ๋งŒ ํฌ๋“œ๋ฅผ ์‚ฌ์šฉํ•˜์—ฌ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ๋‹ค. 

 

 

 

๐Ÿ’ป ์ฝ”๋“œ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import sys
input = sys.stdin.readline
INF = sys.maxsize
 
def bellman(st:int, ed:int, val:int):
    dist = [INF for _ in range(n+1)]
    dist[st] = val
 
    for _ in range(n-1):
        for u,v,w in graph:
            if dist[u] != INF and dist[u] * w < dist[v]:
                dist[v] = dist[u] * w
 
    for u,v,w in graph:
        if dist[u] * w < dist[v]:
            return 0
    return dist[ed]
 
n,m,val,st,ed = input().rstrip().split()
= int(n)
= int(m)
val = float(val)
st = int(st)
ed = int(ed)
graph = []
for _ in range(m):
    u,v,w = map(float,input().split())
    graph.append((int(u),int(v),w))
 
print(bellman(st,ed,val))
 
cs

 

๐Ÿญ ์‹œํ–‰์ฐฉ์˜ค

 

 

๋ฐธ๋ฅ˜ ์—๋Ÿฌ๊ฐ€ ๋ฐœ์ƒํ–ˆ๋˜ ๋ถ€๋ถ„์€ ํ–„๋ฒ„๊ฑฐ์˜ ๊ฐ€๊ฒฉ์„ int ๋กœ ๋ฐ›์•˜๊ธฐ ๋•Œ๋ฌธ์ด์—ˆ๋‹ค. 

 

 

๐Ÿ”— ๋ฌธ์ œ๋งํฌ

 

5942๋ฒˆ: Big Macs Around the World

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 rel

www.acmicpc.net