Submission

Score: 0

User: KantaponZ

Problemset: forex

Language: cpp

Time: 1.010 second

Submitted On: 2026-03-03 21:54:18

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

#define db double

db dp[35][475];
db w[35][35];
int n;
int idx = 0, ct = 1e9;
queue<tuple<int,double,int>> q; // u, ww, ct;

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> w[i][j];
        }
    }

    for (int st = 1; st <= n; st++) {
        for (int i = 0; i < 35; i++) for (int j = 0; j < 475; j++) dp[i][j] = 1;
        q.emplace(st, 1, 0);
        while (!q.empty()) {
            auto [u, ww, ct] = q.front();
            q.pop();
            if (ct + 1 >= 475) continue;
            for (int i = 1; i <= n; i++) {
                if (dp[i][ct+1] < ww * w[u][i]) {
                    dp[i][ct+1] = ww * w[u][i];
                    q.emplace(i, dp[i][ct+1], ct+1);
                }
            }
        }
        for (int i = 1; i <= 471; i++) {
            if (dp[st][i] > 1) {
                if (ct > i) {
                    ct = i;
                    idx = st;
                } else if (ct == i) idx = min(st, idx);
                break;
            }
        }
    }

    if (ct == 1e9) {
        cout << -1;
        return 0;
    }
    cout << idx << " " << ct;
}