Aiuto con police investigation 5

Aiuto
1

Ciao a tutti. Stavo risolvendo Police investigation 5 e, nonostante i testcase di esempio risultino tutti corretti, mi vengono dati errori di Execution killed (could be triggered by violating memory limits) e output non corretto. Il mio codice è il seguente:

#include <iostream>
#include <fstream>
#include <vector>
#include<climits>

using namespace std;
void stampa(vector<vector<int>> G){
    for(int i=0; i<G.size(); i++){
        for(int j=0; j<G[0].size(); j++){
            std::cout<<G[i][j]<<"\t";
        }
        std::cout<<"\n";
    }
}

int dijkstra(vector<vector<int>> &G, int n){
    int m=0, i=0, j=0;
    int x=0, y=n-1;//x=partenza, y=arrivo
    vector<int> d(n,INT_MAX), p(n,-1);
    vector<bool> v(n, false);
    
    d[x]=0;
    p[x]=0;

    while(true) {
        for(m=INT_MAX, i=0; i<n; i++){
            if (!v[i] && d[i] <= m){
                m = d[j=i];
            }
        }
        v[j] = 1;
        if (j == y || m == INT_MAX){
            break;
        }
        for(i=0; i<n; i++){
            if (G[j][i]>=0 && d[i] > d[j] + G[j][i]){
                d[i] = d[j] + G[j][i];
                p[i]=j;
            }
        }   
    }
    
    return d[n-1];
}

int solve(vector<int> &A, vector<int> &B, vector<int> &C, vector<int> &E, int N, int M, int T){
    vector<vector<int>> matrix(N,vector<int>(N,-1));
    int a;
    for(int i=0; i<M; i++){
        if(E[i]==0||(E[i]==1&&C[i]<=T)){
            matrix[A[i]][B[i]]=C[i];
        }
    }
    //stampa(matrix);
    a=dijkstra(matrix, N);
    if(a>=INT_MAX){
        return -1;
    }
    return a;
}

int main() {
    int N, M, T;
    int answer=0;
    ifstream fin("input.txt");
    ofstream fout("output.txt");

    fin >>N>> M>>T;
    vector<int> A(M), B(M), C(M), E(M);

    for (int i=0; i<M; i++){
        fin >>A[i]>>B[i]>>C[i]>>E[i];
    }
    answer=solve(A,B,C,E,N,M,T);

    fout << answer << "\n"; // print the result
    return 0;
}

Gentilmente qualcuno protrebbe aiutarmi, per esempio fornendomi dei testcase dove sbaglio?
Grazie in anticipo.

EDIT: ho ottenuto un 20/100 passando la matrice G per riferimento, come si può vedere nel codice sopra (aggiornato), ma ci sono dei testcase dove il mio output non è corretto

1 Mi Piace
2

Il problema sta nel modo in cui stori le informazioni sugli archi. Prova ad usare una lista di adiacenza.

3

Ciao, grazie della risposta. Sai se c’è qualche spiegazione su un’implementazione della lista di adiacenza? Se sì, potresti passarmi un link?

4

Ciao, se ancora non l’hai usata, ti suggerisco di provare la piattaforma AlgoBadge: offre un percorso guidato per prepararsi alle OII, con link a lezioni e dispense utili alla risoluzione di gran parte dei problemi. In particolare, ti suggerisco di consultare la sezione grafi. Se ti può essere d’aiuto, su Wikipedia puoi trovare un articolo dedicato a questo argomento.

In più, questa lezione dello stage del 2020 tratta (fino al minuto 15) delle liste di adiacenza.

Spero di essere stato d’aiuto, buona serata!

1 Mi Piace
5

Grazie del consiglio… comunque il video l’avevo già guardato e ho capito in cosa consistono le liste di adiacenza, ma cercavo un’implementazione che potessi comprendere, e che non usasse le std::list che ho visto ovunque su internet e che non sono riuscito a capire. Alla fine mi sono implementato in autonomia la lista di adiacenza e la funzione di dijkstra in c++ modificando quella che si trova in questa dispensa (quella sulle matrici di adiacenza, non la lista). Ho poi trovato un errore nel mio ragionamento originale, dove consideravo le strade non percorribili se C[i]<=T, anzichè considerare il fatto che la somma delle strade percorse deve essere <=T.
Grazie comunque dei consigli e buona serata :grin:

6

Sono contento che tu sia riuscito a risolvere, se hai bisogno di aiuto riguardo il codice, condividilo pure! Buona serata :slight_smile:

7

Bè, a questo punto sarei curioso di sapere cosa cambia effettivamente tra utilizzare uno std::vector e una std::list, dato che non ho trovato una spiegazione “potabile” su internet oltre a “std::list is a container that supports constant time insertion and removal of elements from anywhere in the container.”
La mia implementazione è la seguente (con la parte di codice specifica a Police investigation 5 commentata):

struct path{    //struttura che memorizza gli archi del grafo con le caratteristiche necessarie per questo problema; normalmente basterebbero i primi 2 elementi
    int dest;
    int cost;
    /*int explodes;*/
};

int dijkstra(vector<vector<path>> list, int n, int T){
    int m=0, i=0, j=0, temp;
    int x=0, y=n-1;//x=partenza, y=arrivo
    vector<int> d(n,INT_MAX);
    vector<bool> v(n, false);
    
    d[x]=0;

    while(true) {
        for(m=INT_MAX, i=0; i<n; i++){
            if (!v[i] && d[i] <= m){
                m = d[j=i];
            }
        }
        v[j] = 1;
        if (j == y || m == INT_MAX){
            break;
        }
        temp=list[j].size();
        for(i=0; i<temp; i++){
            if(d[list[j][i].dest]>d[j]+list[j][i].cost/*&&(list[j][i].explodes==0||(list[j][i].explodes==1&&d[j]+list[j][i].cost<=T))*/){
                d[list[j][i].dest]=d[j]+list[j][i].cost;
            }
        }
    }
    
    return d[y];
}

C’è qualcosa di strano a usare una versione leggermente modificata dell’algoritmo sulle matrici anziché una totalmente differente? Ho commesso degli “strafalcioni” evidenti?

8

Rispetto ad un vector o altri contenitori simili una list è più veloce nel l’inserimento e nella rimozione di elementi in ogni posizione. Lo fa in tempo costante, mentre i vector lo fanno in tempo lineare. Questo perché, semplificando, in una list ogni elemento ha puntatori all’elemento precedendo e/o successivo. Quindi è facile inserire un elemento in mezzo, ma non supporta l’accesso ad un elemento dato il suo indice, mentre il vector si. Per accedere al quinto elemento di una lista, per esempio, devi iterare partendo dal primo elemento. Nel caso della lista di adiacenza, ti serve solo iterare sui nodi raggiungibili da un certo nodo, quindi può convenire usare una list invece di un vector. Di fatto in pratica cambia poco.

1 Mi Piace