Submission

Score: 0

User: august

Problemset: forex

Language: cpp

Time: 0.050 second

Submitted On: 2026-03-15 21:32:39

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

#define pi pair<int,int>

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin>> n;

    vector<vector<double>> g(n+1, vector<double>(n+1));
    for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) cin>> g[i][j];

    int ans = INT_MAX, id=-1;
    for (int i=1; i<=n; i++) {
        
        int l=1, r=900;
        while (l<=r) {
            int mid=(r-l)/2+l;

            priority_queue<pair<double, pi>, vector<pair<double, pi>>, less<pair<double, pi>>> pq;
            vector<double> dist(n+1, 0.00);
            pq.push({1.0000, {1, i}});
            dist[i] = 1.0000000;

            while (!pq.empty()) {
                pair<double, pi> cur=pq.top();
                pq.pop();
                double d=cur.first;
                int cnt = cur.second.first, u=cur.second.second;

                if (d < dist[u] || cnt==mid+1) continue;

                for (int v=1; v<=n; v++) {
                    if (dist[v] < dist[u]*g[u][v]) {
                        dist[v] = dist[u]*g[u][v];
                        pq.push({dist[v], {cnt+1, v}});
                    }
                }
            }

            //cout<< dist[i]<<'\n';
            if (dist[i] <= 1.000000000) l=mid+1;
            else {
                if (ans > mid) {
                    ans = mid;
                    id = i;
                }
                r=mid-1;
            }
        } 
    }
    if (id==-1) cout<< id;
    else cout<< id<< ' '<<ans;
}