AtCoder Regular Contest 015 C - 変わった単位

問題

　いくつかの単位換算表を与えるので最も大きい単位を最も小さい単位で表したときの関係を示せ。

解法

　ある単位から見ての他の単位の大きさを深さ優先探索で求めて、一番大きいものと一番小さいものを出力する。

反省

　2時間ほどでAC。最初はワーシャルフロイド法でやれると思ったが、小さいほうから大きいほうへ遷移する可能性を考えていなくてWA。結局1時間ほどたってしまったので解説や他の人のブログなどを読んで上の解法に行き着いたが、の場合でバグるコードを書いてしまいそれでずっとハマっていた。その原因に気づくまでに1時間くらいかかりこんな時間に。とてもつらかった……。

　解法としては野田さんのブログをほぼ写した感じで終わり。DFSをスタックで書いた経験が少なくて結構戸惑ってしまった。いつも再帰関数で書いているが、むしろこうやってデータ構造使う方が本筋という気もするし、書こうと思ったときにパッと書けないのはひどい。もっと精進せねば。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N;
    cin >> N;

    vector<string> large(N), small(N);
    vector<double> m(N);
    ll cnt = 0;
    map<string, ll> string2num;
    for (ll i = 0; i < N; i++) {
        cin >> large[i] >> m[i] >> small[i];
        if (string2num.find(large[i]) == string2num.end()) {
            string2num[large[i]] = cnt++;
        }
        if (string2num.find(small[i]) == string2num.end()) {
            string2num[small[i]] = cnt++;
        }
    }

    vector<vector<pair<ll, double>>> connect(cnt);
    for (ll i = 0; i < N; i++) {
        connect[string2num[large[i]]].push_back({ string2num[small[i]], m[i] });
        connect[string2num[small[i]]].push_back({ string2num[large[i]], 1.0 / m[i] });
    }

    vector<double> cost(cnt, 0.0);
    cost[0] = 1.0;
    vector<ll> stack;
    stack.push_back(0);
    while (!stack.empty()) {
        ll curr = stack.back();
        stack.pop_back();
        for (auto e : connect[curr]) {
            if (cost[e.first] != 0.0) {
                continue;
            }
            cost[e.first] = cost[curr] * e.second;
            stack.push_back(e.first);
        }
    }

    ll min_index = min_element(cost.begin(), cost.end()) - cost.begin();
    ll max_index = max_element(cost.begin(), cost.end()) - cost.begin();
    ll ans = (ll)round(cost[max_index] / cost[min_index]);

    string max_str, min_str;
    for (auto p : string2num) {
        if (p.second == max_index) {
            max_str = p.first;
        }
        if (p.second == min_index) {
            min_str = p.first;
        }
    }

    cout << 1 << min_str << "=" << ans << max_str << endl;
}