Ciao, ho provato a fare il problema “Le scale di Hogwuarts” solo che non riesco a fare più di 10 punti, tutto il resto il correttore mi dice fuori tempo massimo. Qualcuno per caso è riuscito a fare più punti? Allego il mio codice (ne ho fatto anche un altro senza usare gli oggetti ma stesso risultato) .
Dov’è il codice?
Inoltre sarebbe utile spiegare l’algoritmo
Uh scusa pensavo di averlo incollato :sweat_smile
#include <fstream>
#define INF 999999999
using namespace std;
// Declaring variables
struct arco;
struct nodo;
// Declaring functions
int camminominimo(nodo* n, nodo* fine,int tempo);
int raggiungi (int , int , int* , int*, int*, int*);
int main() {
ifstream in("input.txt", ios::in);
ofstream out("output.txt", ios::out);
int N;
int M;
int* A;
int* B;
int* inizio;
int* fine;
int tempo;
in>>N>>M;
A = new int[M];
B = new int[M];
inizio = new int[M];
fine = new int[M];
for (int i = 0; i < M; i++) {
in>>A[i]>>B[i]>>inizio[i]>>fine[i];
}
//cout<<N;
// Calling functions
tempo = raggiungi(N, M, A, B, inizio, fine);
// Writing output
out<<tempo;
in.close();
out.close();
return 0;
}
class arco{
public:
nodo* next;
int init;
int finit;
};
class nodo{
public:
int val;
int numarc;
arco *archi;
void initia(){
archi= new arco[numarc];
}
};
int raggiungi(int N, int M, int* A, int* B, int* inizio, int* fine){
int k=0; int time=0;
nodo *nodi= new nodo[N];
for (int i=0; i<N; i++){
nodi[i].val=i;
for (int y=0; y<M; y++) if (A[y]==nodi[i].val || B[y]==nodi[i].val) k++;
nodi[i].numarc=k;
nodi[i].initia();
k=0;
for (int y=0; y<M; y++) {
if (A[y]==i){
nodi[i].archi[k].next=nodi+B[y];
nodi[i].archi[k].init=inizio[y];
nodi[i].archi[k].finit=fine[y];
k++;
}
else if(B[y]==i){
nodi[i].archi[k].next=nodi+A[y];
nodi[i].archi[k].init=inizio[y];
nodi[i].archi[k].finit=fine[y];
k++;
}
}
}
time=camminominimo(nodi+0,nodi+(N-1),0);
if (time==INF)time=-1;
return time;
}
int camminominimo(nodo* n, nodo* fine,int tempo){
if (n==fine)return tempo;
else{
int minimo[n->numarc];
int min=INF;
for(int i=0; i<n->numarc; i++){
if (tempo>=n->archi[i].init && tempo<=(n->archi[i].finit)-1) minimo[i]=camminominimo(n->archi[i].next,fine, tempo+1);
else if(tempo<n->archi[i].init) minimo[i]=camminominimo(n->archi[i].next,fine, n->archi[i].init+1);
else if(tempo>=n->archi[i].finit)minimo[i]=INF;
if (minimo[i]<min)min=minimo[i];
}
return min;
}
}
Potresti spiegare più o meno la tua idea? E’ abbastanza difficile da leggere, non capisco che algoritmo hai implementato
1 Mi Piace
Praticamente essendo i vettori paralleli una struttura dati un po’ “limitante” in questo caso, ho deciso di crearmi una struttura nodo e una struttura arco, la funzione raggiungi() (quella data dal template di default) inizializza queste strutture, la funzione camminominimo() è una funzione ricorsiva che mi esplora tutti gli archi del nodo in cui si trova e appunto restituisce il tempo minimo che impiega per arrivare al nodo N-1. Diciamo che è un esplorazione in profondità un po’ modificato.
Odio usare algoritmi già belli e fatti, questo l’ho pensato io… E infatti non funziona… Pensavo di poter usare dijkstra ma per il fatto del peso dell’arco fisso ad 1 e il tempo di esistenza dell’arco variabile la trovavo difficile come cosa
Come mai odi usare algoritmi già belli e fatti? C’è un motivo se bisogna conoscerli 
Comunque dijkstra è la strada giusta per risolvere il problema.
Consiglio:
Se gli archi non sono pesati, perché non usare il tempo come misura?
1 Mi Piace
Perchè il bello di queste prove è proprio lo scovare un nuovo ragionamento. Tra l’altro non so se ci sia una variante ricorsiva di dijkstra. Penso (e la poca esperienza che ho me lo conferma) che l’iterazione su strutture dati dal carattere ricorsivo come gli alberi e i grafi non porti ad un grande giovamento in termini di tempo…
Non ho mai visto un’implementazione ricorsiva di dijkstra.
Teoricamente se puoi fare qualcosa in modo ricorsivo puoi farlo in modo iterativo, e sempre teoricamente in modo ricorsivo dovrebbe essere più veloce (parliamo di pochissimo, comunque, se l’algoritmo è uguale).
1 Mi Piace
Proverò con dijkstra, ma comunque non penso che sia l’esplorazione del grafo a rallentare, ma bensi l’inizializzazione degli oggetti.