#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