Ciao a tutti, sto provando a risolvere questo banalissimo problema (in cui tra l’altro nella gara avevo preso 100/100) ma non capisco perche’ totalizzo 90/100 (sbaglia l’output del testcase 4).
Allego il mio codice
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <vector>
#include <string>
#define ii pair< int, int >
using namespace std;
int n, k, credits[45], sol = 10000000;
vector < ii > grafo[45];
int dfs(int nodo, int sum, vector<bool> &vis)
{
if(sum>=k) return 0;
int best = 100000000;
for(int i=0;i<grafo[nodo].size(); i++)
{
int figlio = grafo[nodo][i].first;
if(!vis[figlio])
{
vis[figlio] = true;
best = min(best, dfs(figlio, sum+credits[figlio], vis) + grafo[nodo][i].second);
vis[figlio] = false;
}
}
return best;
}
int main(){
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
cin >> k >> n;
for(int i=0; i<n; i++)
cin >> credits[i];
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
int att;
cin >> att;
if(att != 0){
grafo[i].push_back({j, att});
}
}
}
vector <bool> vis;
vis.resize(45, false);
for(int i=0; i<n; i++)
{
vis[i]=true;
sol = min(sol, dfs(i, credits[i], vis));
vis[i]=false;
}
cout << sol;
}
In poche parole creo la lista di adiacenza (in input e’ data la matrice di adiacenza) e lancio una dfs (in cui il vettore di visitati e’ passato come parametro alla funzione). Grazie in anticipo.
Ciao, molto probabilmente la tua soluzione è corretta, il problema è il task che ha il testcase 4 malfunzionante. La soluzione da stampare per quel testcase è 10 (soluzione di fatto errata ma ritenuta esatta dal correttore).
Non so bene cosa sia successo, ho ricaricato gli input/output di quel problema, riprovate a mandare
La cosa curiosa è che ho scaricato la soluzione del primo post e l’ho testata in locale e funzionava esattamente come la mia (che pare essere quella ufficiale ), solo che qui sono stati caricati dei testcase sbagliati, un 11 è diventato un 10, sarà stato un raggio cosmico?
sol e best sono inizialmente impostati a 10000000. E’ da intendersi come valore non superabile dal risultato?
Direi di sì, nel testo non c’è scritto quanto tempo impiega al massimo per preparare un esame, però puoi assumere che la risposta non sia un numero molto grande in questo caso. A breve aggiusto il testo e aggiungo la durata massima di ogni esame.
Posso chiedere quale sarebbe la soluzione ufficiale al problema?
Quello che faccio io è, per ogni esame, provare a sceglierlo come primo, poi faccio una ricerca completa per selezionare gli esami successivi e appena finisco i crediti mi fermo. Tutto ciò alla fine si traduce in N visite del grafo per cercare tutti i possibili percorsi aciclici e selezionare il migliore.
Il mio algoritmo è simile, solo che invece di fare una ricerca completa su tutti i possibili percorsi aciclici, faccio partire dijkstra da ognuno dei nodi, considerando il numero di ore come “distanza” tra due nodi, e salvandomi il numero di crediti ottenuti fino a quel punto. Appena mi trovo ad un nodo in cui ho accumulato sufficienti crediti, aggiorno la soluzione se necessario e riparto selezionando un altro nodo come nodo di partenza: facendo così, il testcase 4 veniva corretto quando la soluzione non era quella ufficiale. Come può essere?
Strano, anche a me sembra di aver usato dijkstra allo stesso modo
Hai considerato che il primo esame è sempre “gratuito” e quindi non devi considerare le ore che servono per prepararlo?
EDIT: no, scusa, ho usato una dfs da ogni nodo contando quanti esami mi servivano per superare il numero di crediti.
Con dijkstra c’è un problema, però.
Se ho capito bene l’algoritmo che hai descritto, calcoli sempre il percorso che ti fa usare il minor numero possibile di ore per passare dal nodo A al nodo B.
Supponiamo che il numero di crediti da raggiungere sia 10 e che il percorso più breve dal nodo A al nodo B impieghi 2 ore, ma ti faccia accumulare solo 2 crediti.
Come fai ad essere sicuro che non ce ne sia un altro, sempre dal nodo A al nodo B, che faccia accumulare 11 crediti in 3 ore?
Usando dijkstra, questo percorso sarebbe completamente scartato.
#include < iostream>
#include < fstream>
#include < vector>
#include < queue>
using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");
vector < pair <int, int> > grafo[100];
vector < int > crediti;
int N, K;
int main(){
cin >> K >> N;
for(int i=0; i<N; i++){
int a;
cin >> a;
crediti.push_back(a);
}
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
int a;
cin >> a;
if(a!=0){
grafo[i].push_back(make_pair(j, a));
}
}
}
int sol = 1e7;
for(int n=0; n<N; n++){
priority_queue <pair <pair <int, int>, int>> Q;
Q.push(make_pair(make_pair(0, crediti[n]), n));
while(!Q.empty()){
int topN = Q.top().second;
int credito = Q.top().first.second;
int ora = -Q.top().first.first;
Q.pop();
if(credito>=K){
sol = min(sol, ora);
break;
}
for(pair <int, int> i:grafo[topN]){
if(ora + i.second <= K){
Q.push(make_pair(make_pair(-ora-i.second, credito+crediti[i.first]), i.first));
}
}
}
}
cout << sol;
}
Questo dovrebbe essere più leggibile di quello che ho postato precedentemente, comunque nel codice c’è un baco (avendo scritto anche la soluzione ufficiale non lo ho cercato), infatti fa 90/100.
), solo che qui sono stati caricati dei testcase sbagliati, un 11 è diventato un 10, sarà stato un raggio cosmico?
