Submission

Score: 100

User: kittipos

Problemset: forex

Language: cpp

Time: 0.006 second

Submitted On: 2026-03-09 11:37:27

#include <bits/stdc++.h>

using namespace std;


vector<vector<double>> graph;
int n;
int bfs(int node) {
    vector<double> best;
    best.assign(n, 0);
    queue<pair<int, double>> q; // node and amount
    q.push({node, 1});
    int cnt = -1;
    while (!q.empty()) {
        int chuck = q.size();
        cnt++;
        for (int i = 0; i < chuck; i++) {
            pair<int, double> cur = q.front();
            q.pop();

            // cout << "check point 2, first: " << cur.first << ", second: " << cur.second << ", n: " << n << endl;

            if (cur.first == node && cur.second > 1.01) {
                return cnt;
            }

            if (best[cur.first] >= cur.second) {
                // cout << "continue" << endl;
                continue;
            }

            best[cur.first] = cur.second;

            for (int j = 0; j < n; j++) {
                q.push({j, cur.second * graph[cur.first][j]});
            }
        }
    }
    return INT_MAX;
}

int32_t main() {
    cin >> n;
    graph.assign(n, vector<double>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            double temp;
            cin >> temp;
            graph[i][j] = temp;
        }
    }
    
    pair<int, int> best = {INT_MAX, INT_MAX}; // distance and node
    for (int i = 0; i < n; i++) {
        // cout << "check point 1" << endl;
        best = min(best, {bfs(i), i});
    }

    if (best.first == INT_MAX) {
        cout << -1;
        return 0;
    }
    cout << best.second + 1 << ' ' << best.first<< '\n';



    return 0;
}