# Police Investigation 5 10/100

**URL:** <https://forum.olinfo.it/t/police-investigation-5-10-100/8253>\
**Category:** Aiuto\
**Created:** [13 Maggio 2023, 8:50pm UTC](https://forum.olinfo.it/t/police-investigation-5-10-100/8253 "2023-05-13T20:50:58Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![danieledellef](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/d/c0e974/32.png) [@danieledellef](https://forum.olinfo.it/u/danieledellef)\
**Post date:** [13 Maggio 2023, 8:50pm UTC](https://forum.olinfo.it/t/police-investigation-5-10-100/8253/1 "2023-05-13T20:50:58Z")

</div>

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.

```auto
#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;
}

```

---

<div class="post-metadata">

**Author:** ![fabriziogiacomi](https://forum.olinfo.it/user_avatar/forum.olinfo.it/fabriziogiacomi/32/2523_2.png) [@fabriziogiacomi](https://forum.olinfo.it/u/fabriziogiacomi)\
**Post date:** [14 Maggio 2023, 5:45pm UTC](https://forum.olinfo.it/t/police-investigation-5-10-100/8253/2 "2023-05-14T17:45:11Z")

</div>

Ciao, nell’algoritmo di Dijkstra gli archi vanno ordinati per peso. Se risolvi questo piccolo problema, il codice fulla 🙂  
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!

---

<div class="post-metadata">

**Author:** ![danieledellef](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/d/c0e974/32.png) [@danieledellef](https://forum.olinfo.it/u/danieledellef)\
**Post date:** [14 Maggio 2023, 7:22pm UTC](https://forum.olinfo.it/t/police-investigation-5-10-100/8253/3 "2023-05-14T19:22:17Z")

</div>

Perfetto, grazie mille, tutto chiaro!