Di recente ho provato a fare SunnyDale, la mia idea è quella di prendere per ogni nodo semplicemente i percorsi meno costosi. Il mio codice prende 75/100, sbagliando due subtasks e superando il limite di memoria di altre tre subtasks, qualcuno potrebbe aiutarmi? allego il mio codice
#include <iostream>
#include <utility>
using namespace std;
int main(){
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int numerosvincoli, numeroGall, partenza, arrivo, precedente = -1;
cin >> numerosvincoli >> numeroGall >> partenza >> arrivo;
pair<int, int> gallerie[numeroGall - 1];
for(int i = 0; i < numeroGall; i++){
gallerie[i].second = 1000;
}
int primo, secondo, terzo;
for(int i = 0; i <= numerosvincoli; i++){
cin >> primo >> secondo >> terzo;
primo--;
secondo--;
if(terzo < gallerie[primo].second || gallerie[primo].second < 0){
//cout << "cambio gallerie alla posizione " << primo + 1 << " con " << secondo + 1 << endl;
//cout << "PS sostituisco la luce " << gallerie[secondo].second << " con " << terzo << endl;
gallerie[primo].first = secondo;
gallerie[primo].second = terzo;
} /*else {
cout << "non cambio galleria alla posizione " << primo << "con " << secondo << endl;
}*/
if(gallerie[secondo].second > terzo ){
//cout << "cambio gallerie alla posizione secondo " << secondo + 1 << " con " << primo + 1 << endl;
gallerie[secondo].second = terzo;
gallerie[secondo].first = primo;
}
}
int passaggi = 0;
partenza--;
arrivo--;
if(partenza == arrivo) {
cout << 0 << endl;
return 0;
}
//for(int i = 0; i < numeroGall - 1; i++) cout << "galleria " << i << "collegata a " << gallerie[i].first << endl;
while(partenza != arrivo){
if(gallerie[partenza].first == precedente){
//cout << "sono nella galleria numero " << partenza <<" collegata alla galleria numero " << gallerie[partenza].first + 1 << " è uguale a quella " << precedente << endl;
cout << -1 << endl;
return 0;
} else {
precedente = partenza;
partenza = gallerie[partenza].first;
//cout << "mi sposto da " << precedente<< " a " << partenza << endl;
//cout << "partenza = " << partenza << endl;
passaggi++;
}
}
cout << passaggi << endl;
}
Ciao, utilizza questo input per capire dove sbaglia il codice:
6 8 6 1
2 1 8
1 3 3
3 5 6
4 5 1
6 3 4
1 6 5
2 4 7
5 6 2
La destinazione non è raggiungibile come puoi verificare sulla carta.
ok, adesso proverò a sistemare, ti ringrazio
Adesso ho implementato la risoluzione del tuo input, ma il codice fa ugualmente 75/100
#include <iostream>
#include <utility>
using namespace std;
int main(){
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int numerosvincoli, numeroGall, partenza, arrivo, precedente = -1;
cin >> numerosvincoli >> numeroGall >> partenza >> arrivo;
pair<int, int> gallerie[numeroGall - 1];
for(int i = 0; i < numeroGall; i++){
gallerie[i].second = 1000;
}
int primo, secondo, terzo;
for(int i = 0; i <= numerosvincoli + 1; i++){
cin >> primo >> secondo >> terzo;
primo--;
secondo--;
//cout << "Confronto " << primo + 1 << " con secondo " << secondo + 1 << endl;
if(terzo < gallerie[primo].second || gallerie[primo].second < 0){
//cout << "cambio gallerie alla posizione " << primo + 1 << " con " << secondo + 1 << endl;
//cout << "PS sostituisco la luce " << gallerie[secondo].second << " con " << terzo << endl;
gallerie[primo].first = secondo;
gallerie[primo].second = terzo;
} /*else {
cout << "non cambio galleria alla posizione " << primo << "con " << secondo << endl;
}*/
if(gallerie[secondo].second > terzo ){
//cout << "cambio gallerie alla posizione secondo " << secondo + 1 << " con " << primo + 1 << endl;
gallerie[secondo].second = terzo;
gallerie[secondo].first = primo;
}
}
int passaggi = 0;
partenza--;
arrivo--;
if(partenza == arrivo) {
cout << 0 << endl;
return 0;
}
//for(int i = 0; i < numeroGall - 1; i++) cout << "galleria " << i << "collegata a " << gallerie[i].first << endl;
while(partenza != arrivo){
if(gallerie[partenza].first == precedente){
//cout << "sono nella galleria numero " << partenza <<" collegata alla galleria numero " << gallerie[partenza].first + 1 << " è uguale a quella " << precedente << endl;
cout << -1 << endl;
return 0;
} else {
precedente = partenza;
partenza = gallerie[partenza].first;
//cout << "mi sposto da " << precedente<< " a " << partenza << endl;
//cout << "partenza = " << partenza << endl;
passaggi++;
}
}
cout << passaggi << endl;
}
Ciao, ho rivisto il tuo codice e ci sono alcune righe da correggere per risolvere il problema:
-
pair<int, int> gallerie[50010]; invece di pair<int, int> gallerie[numeroGall - 1]; altrimenti ti dà errore di memoria.
-
for(int i=0; i < numeroGall; i++) { gallerie[i].second = 0; } invece di for(int i=0; i < numeroGall; i++) { gallerie[i].second = 1000; }
diversamente dichiari pair<int, int> gallerie[50010] globalmente. -
l’errore più serio: for(int i = 0; i<numeroGall; i++) {} invece di for(int i = 0; i <= numerosvincoli + 1; i++) {}
-
per impostare correttamente il grafo si deve mettere:
if(terzo < gallerie[primo].second || gallerie[primo].second == 0) {} e
if(gallerie[secondo].second > terzo || gallerie[secondo].second ==0) {}
okok, provo a correggere
ti ringrazio, adesso prendo 100/100, mi potresti spiegare che cambia se assegno un numero fisso rispetto a una variabile?
Non cambia niente, si può fare solo in locale e fare, comunque, attenzione al giusto dimensionamento. Mi veniva errore di memoria e ho utilizzato il valore massimo del problema. Volendo si può riutilizzare la variabile al posto della costante.
va bene, ti ringrazio