Di recente ho provato a risolvere il problema cammino minimo.
Ho provato esattamente in tre modi. Per prima cosa ho provato implementando Belman Ford, ma l’algoritmo era troppo lento. Dopo di che sono passato a Djikstra, notando che implementando Djikstra, il codice aveva ugualmente dei testcase errati. Dopo un analisi del problema sono arrivato a questo argomento, che dà ugualmente 0/100. Cosa sto sbagliando?
#include <vector>
#include<utility>
using namespace std;
struct struttura{
vector<pair<int, int>> collegamenti;
int entrata = 0;
bool passato = false;
bool collegatoazero = false;
};
void mincammino(int N, int M, vector<int> X, vector<int> Y, vector<int> P, vector<int> &D) {
vector<struttura> nodo(N);
pair<int, int> a;
nodo[0].collegatoazero = true;
for(int i = 0; i < M; i++){
nodo[Y[i]].entrata++;
a.first = Y[i];
a.second = P[i];
nodo[X[i]].collegamenti.push_back(a);
if(nodo[X[i]].collegatoazero) nodo[Y[i]].collegatoazero;
}
int posizionetop = 0;
D[0] = 0;
while(posizionetop < N){
for(int i = 0; i < N; i++){
if(nodo[i].entrata == 0){
for(int l = 0; l < nodo[i].collegamenti.size(); l++){
//cout << i << " : i " << D[i] << " : COSTO I " << nodo[i].collegamenti[l].first << ": PEKO PAIN " << D[i] + nodo[i].collegamenti[l].second << " : COSTO"<< endl;
nodo[nodo[i].collegamenti[l].first].entrata--;
if(nodo[i].collegatoazero && (nodo[nodo[i].collegamenti[l].first].passato == false || D[nodo[i].collegamenti[l].first] > D[i] + nodo[i].collegamenti[l].second)){
D[nodo[i].collegamenti[l].first]= D[i] + nodo[i].collegamenti[l].second;
nodo[nodo[i].collegamenti[l].first].passato = true;
nodo[nodo[i].collegamenti[l].first].collegatoazero = true;
}
}
nodo[i].entrata = -1;
break;
}
}
posizionetop++;
}
/*for(int i = 0; i < N; i++){
cout << nodo[i].passato << endl;
}*/
D[0] = 0;
for(int i = 1; i < N; i++) if(nodo[i].passato == false) D[i] = -1;
}
Il task è stato aggiornato, sono stati aggiunti nuovi subtask e alcuni testcase sono stati modificati pertanto la tua soluzione potrebbe prendere un punteggio diverso.
scusatemi, ma il mio codice è un classicissimo dijkstra, non vedo per quale motivo non dovrebbe prendere punteggio pieno. Sbaglia completamente il 3 subtask…
#include <bits/stdc++.h>
using namespace std;
struct arco {
int fine;
int peso;
};
void mincammino(int N, int M, vector<int> X, vector<int> Y, vector<int> P, vector<int> &D) {
vector<arco> list[N];
D.resize(N);
// Build adjacency list
for (int i = 0; i < M; i++) {
arco tmp;
tmp.fine = Y[i];
tmp.peso = P[i];
list[X[i]].push_back(tmp);
D[X[i]] = -1;
D[tmp.fine] = -1;
}
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push(make_pair(0, 0));
D[0] = 0;
while (!pq.empty()) {
int nodo = pq.top().second;
pq.pop();
for (arco next: list[nodo]) {
if (D[nodo] + next.peso < D[next.fine] || D[next.fine] == -1) {
D[next.fine] = D[nodo] + next.peso;
pq.push(make_pair(D[next.fine], next.fine));
}
}
}
}
altrimenti qualche distanza non viene inizializzata correttamente.
la tua implementazione dell’algoritmo di Dijkstra salta la distanza in cima alla pq, pertanto devi considerare la distanza dist = pq.top().first e confrontarla con con i nodi adiacenti della lista.
