백준 26000 (C++) Imperfect Imperial Units

최초 업로드: 2025-09-21 08:14:11

최근 수정 시간: 2025-09-21 08:15:04

게시자: rlatjwls3333

카테고리: 백준

# [Gold III] Imperfect Imperial Units

[문제 링크](https://www.acmicpc.net/problem/26000)

## 문제 설명

You are writing a paper for the Beta Astronomy Physics Conference about your recent discovery on grey holes. One of your collaborators has performed a huge number of measurements, which you would like to analyse in order to draw some conclusions. The only problem is: the data is measured in a wide variety of units, and to your disgust, they appear to use a mix of the imperial and metric systems. To simplify your analysis, you need to convert all these measurements into a different unit.

## 입력

The input consists of:

<ul>
	<li>One line with two integers $n$ and $q$ ($1\leq n\leq 100$, $1\leq q\leq 10\,000$), the number of unit conversion equations and the number of queries to answer.</li>
	<li>$n$ lines, each defining a unit conversion in the format "<code>1 <unit> = <value> <unit></code>".</li>
	<li>$q$ lines, each with a query in the format "<code><value> <unit> to <unit></code>".</li>
</ul>

In these formats, "<code><value></code>" is a floating-point number $v$ ($0.001 \leq v \leq 1000$, with at most $9$ digits after the decimal point) and "<code><unit></code>" is a string of at most $20$ English lowercase letters (<code>a-z</code>). A unit in a query is guaranteed to be defined in at least one unit conversion equation. Every unit can be converted into every other unit in at most one way.

## 출력

For every query, output the value of the requested unit, or "<code>impossible</code>" if the query cannot be answered.

Your answers should have a relative error of at most $10^{-6}$.

## 풀이
모든 간선을 입력받고, 모든 정점에 대해 다른 모든 정점으로 dfs를 한번씩 해서 방문 가능한 모든 정점을 매핑하고 이동 가능하면 출력하면 됩니다. 
여기서 변환한 값을 출력해줄 때, fixed << setprecision 을 쓰는 것이 아닌 << setprecision 만 써줘야 합니다. fixed를 사용하면 실수 오차로 틀립니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

typedef long double ld;
map<pair<string, string>, ld> res;
map<string, vector<pair<string, ld>>> conn;

set<string> vis;
string root;

void dfs(string cur, ld w) {
    res[{root, cur}]=w;
    for(auto next : conn[cur]) {
        if(!vis.count(next.first)) {
            vis.insert(next.first);
            dfs(next.first, w*next.second);
        }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, q; cin >> n >> q;
    while(n--) {
        ld a, b; string sa, sb; cin >> a >> sa >> sb >> b >> sb;
        conn[sa].push_back({sb, b});
        conn[sb].push_back({sa, 1/b});
    }
    for(auto c : conn) {
        root = c.first;
        vis = {};
        dfs(c.first, 1);
    }

while(q--) {
 ld a; string sa, sb; cin >> a >> sa >> sb >> sb;
 if(!res.count({sa, sb})) cout << "impossible\n";
 else cout << setprecision(15) << res[{sa, sb}]*a << '\n';
 }
}
```