Ciao a tutti,
Sto provando a risolvere il problema sunnydale ma prendo solo 45/100, alcuni testcase danno “Execution killed with signal 9 (could be triggered by violating memory limits)”, altri danno “Execution timed out”, ma quest’ultimo mi sembra strano dato che il mio algoritmo ha complessità O(n).
Vi lascio il link del codice, grazie a chi mi darà una mano 
La violazione dei limiti di memoria (di 256 Mib) è dovuta alla complessità in memoria della tua implementazione, che è pari a O(n^2) per via della matrice g di n righe e n colonne.
Per ovviare a questo problema potresti usare delle liste di adiacenza, al posto della matrice delle adiacenze.
Ci sono anche alcuni errori di logica nella tua implementazione che causano timeout e output non corretti, e che lascio trovare a te a partire da alcuni esempi (prova prima da solo, ma se hai bisogno di aiuto chiedi pure).
Ecco due casi che puoi usare per controllare:
3 3 1 3
1 3 3
2 3 2
1 2 1
3 2 1 3
1 2 3
2 3 1
1 Mi Piace
Come faccio a rappresentare un grafo pesato con le liste?
Immagino che potrei usare un vector<pair<int,int>>, è giusto?
E poi questo comando ad esempio,
if(g[partenza][i] == 0 || g[partenza][i] == -1) continue;
Come diventerebbe? Così per esempio?
if(g[i].second == 0 || g[i].second == -1) continue;
Esatto, l’idea è quella di usare i pair, con ogni pair che contiene il punto di arrivo di un arco e il suo peso.
Ad esempio per creare il grafo a partire dall’input del problema puoi fare così:
vector < vector < pair < int , int > > > g(N);
for (int i = 0; i < M; i++)
{
int a, b, w;
cin >> a >> b >> w
a--; b--;
g[a].push_back({b, w});
g[b].push_back({a, w});
}
Quella riga di codice non ti serve più, dato che non ci sono collegamenti di peso 0 o -1.
1 Mi Piace
Giusto!
Però devo fare il confronto per vedere quale è meno luminoso…
Come posso farlo?
if(g[i].second < min)
Quindi ho pensato di lasciare if(g[partenza][i].second < min) ma il programma si blocca.
Come posso fare?
In che senso si blocca?
Manda la versione più aggiornata del tuo programma così posso aiutarti.
Per inserire il codice nel messaggio puoi racchiuderlo fra i tripli apici ```, così si ottiene il formato corretto
Edit: forse si blocca perché il ciclo non deve più andare da 0 a n, ma da 0 a g[partenza].size()
1 Mi Piace
#include <bits/stdc++.h>
using namespace std;
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
int n,m,h,s;
cin>>n>>m>>h>>s;
vector < vector < pair < int , int > > > g(n);
for (int i = 0; i < m; i++)
{
int a, b, w;
cin >> a >> b >> w;
a--; b--;
g[a].push_back({b, w});
g[b].push_back({a, w});
}
int partenza = h-1;
int indiceMin;
int min = 50001;
int ans = 0;
if(h == s)
{
cout<<ans<<endl;
return 0;
}
for(int i=0;i<g[partenza].size();i++)
{
if(partenza == s-1)
{
cout<<ans<<endl;
return 0;
}
if(g[partenza][i].second < min)
{
min = g[partenza][i].second;
indiceMin = i;
}
if(i == n-1)
{
min = 50001;
i=-1;
ans++;
partenza = indiceMin;
}
}
cout<<-1<<endl;
}
Ci sono due errori nella implementazione:
indicemin = i diventa indicemin = g[partenza][i].first, dato che il primo elemento della coppia è il punto di arrivo dell’arco
Devi poi cambiare n in g[partenza].size() anche nell’ultimo if, quindi
if(i == n-1) diventa if(i==g[partenza].size()-1)
Fatti questi aggiustamenti, il codice è corretto, ma manca ancora qualcosa dato che in alcuni casi entra in un loop infinito (riesci a capire come mai?)
Soluzione: tieni traccia dei nodi visitati tramite un vector<bool>, quando ti trovi in un nodo già visitato esci dal ciclo
1 Mi Piace