Piano di studi 90/100

#include <bits/stdc++.h>

using namespace std;

int K, N, Crediti[30], Res = 9999999;
vector <pair <int, int>> Adj[30];

void DFS(int S, int Calcolo, int Cred, vector <bool> V) {

    if(Calcolo >= Res) return;

    if(Cred >= K)  {

        Res = min(Res, Calcolo);
        return;
    }

    if(V[S]) return;
    V[S] = 1;

    for(auto i : Adj[S]) DFS(i.first, Calcolo+i.second, Cred+Crediti[i.first], V);
}

int main() {

    ios::sync_with_stdio(0);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    cin >> K >> N;
    for(int i = 0; i < N; i++) cin >> Crediti[i];
    for(int i = 0; i < N; i++)
    for(int j = 0; j < N; j++) {

        int a; cin >> a;
        if(a == 0) continue;
        else Adj[i].push_back({j, a});
    }

    for(int i = 0; i < N; i++) {

        vector <bool> V(30, 0);
        DFS(i, 0, Crediti[i], V);
    }

    cout << Res;
}

Buonasera stavo risolvendo questo problema a mi risulta un output errato al test case 4. Avevo già letto altri post riguardo a questo problema i quali dicevano che il test case 4 potesse avere una risposta sbagliata considerata corretta però dal correttore ma non ho capito se il problema è stato risolto oppure il mio algoritmo si intoppa proprio in quel test case. Se l’ultima ipotesi fosse corretta vorrei cercare di capire dove sia l’errore. L’idea è quella di costruirsi un grafo andando a considerare ogni nodo come il primo esame e per ognuno di essi eseguire una DFS e salvarmi il risultato migliore. Grazie

Con una piccola modifica va
metti

come prima istruzione della DFS (altrimenti la DFS fa qualcosa di troppo anche su vertici già visitati)
Ho visto che funziona anche togliendo (cosa che sarebbe bene fare comunque) dalla lista delle adiacenze di un vertice il vertice stesso. Evidentemente almeno per il test case 4 a[i][i] non vale sempre 0.

in

if(a == 0 || i==j) continue;

Hai ragione grazie mi era sfuggita questa piccola cosa.