Tax avoidance (tax)

Aiuto
1

Ho fatto quest’algoritmo, e tutti i testcase tranne uno, il numero 10, vanno:

cin>>n>>m;

    vector<pair<int, float>> adj[n]; //adj[nodo attuale] = {nodo di arrivo, peso}
    
    for(int i = 0; i < m; ++i){
        int a, b; float w; cin >> a >> b >> w;
        adj[a].push_back({b, w}); 
    }

    pi best = {0, 0};
    float best_saldo = 1000;

    for(int i = 0; i < n; ++i){
        vector<float> saldo(n, 0);
        priority_queue<pair<float, int>> q; //{-distanza, nodo di arrivo}
        vector<bool> processed(n, false);
        
        saldo[i] = 1000; // saldo[nodo di partenza] = 0
        q.push({1000, i});
        
        while (!q.empty()) {
            int a = q.top().second; q.pop();
        
            if (processed[a]) continue;
            processed[a] = true;
        
            for (auto u : adj[a]) {
                int b = u.first; float w = u.second;
        
                if (saldo[a] * ((float)1 - w / (float)1000) > saldo[b]) {
                    saldo[b] = saldo[a] * ((float)1 - w / (float)1000);
                    q.push({saldo[b], b});
                }
            }
        }

        for(int j = 0; j < n; ++j){
            if(saldo[j] < best_saldo){
                best = {i, j};
                best_saldo = saldo[j];
            }
        }
            
    }

    cout << best.first << " " << best.second << endl;

    return 0;
}

l’algoritmo è semplicemente l’algoritmo di dijkstra ripetuto per ogni nodo, e mi trovo la soluzione in questo modo. Tranne per quell’unico testcase. Chiedo aiuto.

2

È solo una questione di precisione in virgola mobile.

3

ah non ci ho proprio pensato, grazie