Police Investigation 5 10/100

Salve ragazzi, stavo provando a risolvere Police Investigation 5 ma riesco solo a fare 10/100 per output errato, ho implementato semplicemente l’algoritmo di dijkstra con la condizione extra richiesta dal problema ma alcuni testcase me li restituisce errati. Ho modificato anche il template fornito per utilizzare le liste di adiacenza.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main()
{
    int N,A,T,start,end,peso,esp;
    cin>>N>>A>>T;
    
    int visitato[N],dist[N];
    
    vector<vector<pair<int,int>>> adj(N);
    vector<vector<int>> esploso(N);
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
    
    for(int i=0;i<N;i++){
        visitato[i]=0;
        dist[i]=2147483647;
    }
    
    for(int i=0;i<A;i++){
        cin>>start>>end>>peso>>esp;
        adj[start].push_back(pair<int,int>(end,peso));
        esploso[start].push_back(esp==1 ? T:2147483647);
        
    }
    
    pq.push(pair<int,int>(0,0));
    dist[0]=0;
    
    while(!pq.empty()){
        pair<int,int> anal=pq.top();
        pq.pop();
        
        if(visitato[anal.first]==0){
            visitato[anal.first]=1;
            
            for(int i=0;i<adj[anal.first].size();i++){
                pair<int,int>next=adj[anal.first][i];
                
                if(dist[next.first]>dist[anal.first]+next.second){
                    
                    if(dist[anal.first]+next.second<=esploso[anal.first][i]){
                        dist[next.first]=dist[anal.first]+next.second;
                        pq.push(pair<int,int>(next.first,dist[next.first]));
                        
                    }
                }
            }
        }
    }
    
    if(dist[N-1]==2147483647)dist[N-1]=-1;
    cout<<dist[N-1];
    
    return 0;
}

Ciao, nell’algoritmo di Dijkstra gli archi vanno ordinati per peso. Se risolvi questo piccolo problema, il codice fulla :slight_smile:
Ne ho anche approfittato per mettere qualche suggerimento sul codice in generale (che è solo di stile, non è obbligatorio seguirli, ovviamente).

Hai bisogno di aiuto? Ecco un suggerimento: pq.push(pair<int,int>(next.first,dist[next.first])) deve diventare pq.push(pair<int, int>(dist[next.first], next.first)). In questo modo la priority queue sarà ordinata per distanza (primo elemento della coppia). Importante: aggiorna conseguentemente anche tutti gli accessi al contenuto di pq.top() (quindi trasformando anal.first in anal.second).

Suggerimenti di stile

Qualche indicazione nel futuro, per scrivere meno codice:

  • Al posto di usare funzioni tipo container.push(pair<int, int>(a, b)), puoi usare container.push(make_pair(a, b)) oppure container.push({a, b}). Il mio consiglio è quello di usare container.emplace(a, b): con questo metodo il container cercherà di costruire l’elemento che stai cercando di aggiungere (in questo pair<int, int>, ma funziona anche con altri tipi).
    • N.B. con container intendo un qualsiasi container della stl; il metodo push rappresenta un qualsiasi metodo che implementi quell’azione (quindi push_back etc). Vale lo stesso per emplace.
  • Quando devi definire un infinito, crea una variabile globale al posto di usare lo stesso valore numerico più volte: in questo modo è più semplice da comprendere il codice!
    • Se vuoi, nella librireria limits sono definiti numerosi limiti, in particolare per i numeri puoi usare std::numeric_limits<type>::max() o ::min() per ottenere, rispettivamente, il massimo e il minimo valore che può assumere un numero di tipo type (ad es. int o long long).

Spero di essere stato d’aiuto, buona serata!

1 Mi Piace

Perfetto, grazie mille, tutto chiaro!