# 2 problemi nell'implementazione dijkstra

**URL:** <https://forum.olinfo.it/t/2-problemi-nellimplementazione-dijkstra/5490>\
**Category:** Aiuto\
**Created:** [24 Dicembre 2018, 3:02pm UTC](https://forum.olinfo.it/t/2-problemi-nellimplementazione-dijkstra/5490 "2018-12-24T15:02:45Z")\
**Posts on this page:** 11\
**Page:** 2

<div class="post-metadata">

**Author:** ![v.bizzarri](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/v/7c8e57/32.png) [@v.bizzarri](https://forum.olinfo.it/u/v.bizzarri)\
**Post date:** [25 Dicembre 2018, 12:00pm UTC](https://forum.olinfo.it/t/2-problemi-nellimplementazione-dijkstra/5490/21 "2018-12-25T12:00:46Z")

</div>

Semplicemente c’è scritto:

> Risolvete Dijkstra su un grafo diretto

Buon Natale

---

<div class="post-metadata">

**Author:** ![shine](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/s/77aa72/32.png) [@shine](https://forum.olinfo.it/u/shine)\
**Post date:** [25 Dicembre 2018, 4:09pm UTC](https://forum.olinfo.it/t/2-problemi-nellimplementazione-dijkstra/5490/22 "2018-12-25T16:09:47Z")

</div>

Ho provato a cambiare e mettere tutto in long long eppure prende comunque 95/100 😕

---

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [25 Dicembre 2018, 6:19pm UTC](https://forum.olinfo.it/t/2-problemi-nellimplementazione-dijkstra/5490/23 "2018-12-25T18:19:43Z")

</div>

Controlla di aver cambiato tutto? L’ultimo testcase mettendo i long long int a me lo faceva correttamente anche con gli archi bidirezionali.

---

<div class="post-metadata">

**Author:** ![shine](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/s/77aa72/32.png) [@shine](https://forum.olinfo.it/u/shine)\
**Post date:** [25 Dicembre 2018, 6:40pm UTC](https://forum.olinfo.it/t/2-problemi-nellimplementazione-dijkstra/5490/24 "2018-12-25T18:40:07Z")

</div>

[https://pastebin.com/f4CGsQfa](https://pastebin.com/f4CGsQfa) 95/100

---

<div class="post-metadata">

**Author:** ![filippos](https://forum.olinfo.it/user_avatar/forum.olinfo.it/filippos/32/103_2.png) [@filippos](https://forum.olinfo.it/u/filippos)\
**Post date:** [25 Dicembre 2018, 6:58pm UTC](https://forum.olinfo.it/t/2-problemi-nellimplementazione-dijkstra/5490/25 "2018-12-25T18:58:50Z")

</div>

Linea 32: `distanze[i]=1e9;`

1e9 (aka 1 miliardo) non è abbastanza per rappresentare nodi a distanza infinito, in quanto è teoricamente possibile avere nodi a distanza (N-1) \times MAXP 🙂

---

<div class="post-metadata">

**Author:** ![shine](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/s/77aa72/32.png) [@shine](https://forum.olinfo.it/u/shine)\
**Post date:** [25 Dicembre 2018, 7:00pm UTC](https://forum.olinfo.it/t/2-problemi-nellimplementazione-dijkstra/5490/26 "2018-12-25T19:00:47Z")

</div>

Cosa sarebbe MAXP?

Comunque, con cosa sostituisco “1e9”?

---

<div class="post-metadata">

**Author:** ![filippos](https://forum.olinfo.it/user_avatar/forum.olinfo.it/filippos/32/103_2.png) [@filippos](https://forum.olinfo.it/u/filippos)\
**Post date:** [25 Dicembre 2018, 7:10pm UTC](https://forum.olinfo.it/t/2-problemi-nellimplementazione-dijkstra/5490/27 "2018-12-25T19:10:18Z")

</div>

> [@shine](#):
>
> Cosa sarebbe MAXP?

Il valore massimo di P nel problema, e penso che sia 10^6 se ho contato bene gli zeri.

> [@shine](#):
>
> Comunque, con cosa sostituisco “1e9”?

Siccome N = 10^4, puoi usare un qualsiasi valore \ge 10^{10}, oppure puoi rendere la cosa un po’ più generalizzata e usare qualcosa come `n * (long long) *max_element(p.begin(), p.end())`, dove `p` è un `vector<int>` contenente tutti i pesi degli archi; questo perché una _shortest path_ non conterrà mai più di N-1 archi.  
Volendo, puoi anche usare la somma dei pesi di tutti gli archi, a seconda di quale metodo ti sembra più semplice e intuitivo 🙂

---

<div class="post-metadata">

**Author:** ![shine](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/s/77aa72/32.png) [@shine](https://forum.olinfo.it/u/shine)\
**Post date:** [25 Dicembre 2018, 7:11pm UTC](https://forum.olinfo.it/t/2-problemi-nellimplementazione-dijkstra/5490/28 "2018-12-25T19:11:49Z")

</div>

“Volendo, puoi anche usare la somma dei pesi di tutti gli archi, a seconda di quale metodo ti sembra più semplice e intuitivo” Provo questo, mi sembra piu semplice

---

<div class="post-metadata">

**Author:** ![shine](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/s/77aa72/32.png) [@shine](https://forum.olinfo.it/u/shine)\
**Post date:** [25 Dicembre 2018, 7:13pm UTC](https://forum.olinfo.it/t/2-problemi-nellimplementazione-dijkstra/5490/29 "2018-12-25T19:13:15Z")

</div>

Grazie mille: funziona

---

<div class="post-metadata">

**Author:** ![v.bizzarri](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/v/7c8e57/32.png) [@v.bizzarri](https://forum.olinfo.it/u/v.bizzarri)\
**Post date:** [25 Dicembre 2018, 11:26pm UTC](https://forum.olinfo.it/t/2-problemi-nellimplementazione-dijkstra/5490/30 "2018-12-25T23:26:48Z")

</div>

puoi anche usare LLONG\_MAX cioè il massimo valore che si può assegnare ad una variabile long long.  
Magari in testa metti:

> #include \<stdint.h\>  
> #include \<limits.h\>

---

<div class="post-metadata">

**Author:** ![v.bizzarri](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/v/7c8e57/32.png) [@v.bizzarri](https://forum.olinfo.it/u/v.bizzarri)\
**Post date:** [27 Dicembre 2018, 1:03pm UTC](https://forum.olinfo.it/t/2-problemi-nellimplementazione-dijkstra/5490/31 "2018-12-27T13:03:52Z")

</div>

Solo per completezza di discussione:  
Se vuoi usare quel trucco delle distanze negative puoi ma non te la cavi semplicemente salvando le distanze cambiate di segno, troppo comodo ma non funziona. Tutte le distanze, comprese quelle che leggi da input vanno cambiate di segno, devi usare -infinito (-1e9) e cambiare il verso della disequazione etc…  
Inoltre il primo elemento del pair deve essere la distanza non il nodo (come poi hai fatto nella seconda versione) e la condizione del while …  
Detto ciò il codice sotto riportato fa 95/100

```auto
#include <iostream>
#include <queue>
#include <vector>
#include<fstream>
#define MAXN 10000
using namespace std;
int main(){
    ifstream in;
    ofstream ou;
    in.open("input.txt");
    ou.open("output.txt");
    int nodi,archi,nodoiniziale,nododaraggiungere;
    in>>nodi;
    vector<pair<int,int>> v[MAXN];
    in>>archi;
    in>>nodoiniziale;
    nodoiniziale--;
    in>>nododaraggiungere;
    nododaraggiungere--;
    int a,b,c;
    for(int i=0;i<archi;i++){
        in>>a;
        in>>b;
        in>>c;
        a--;
        b--;
        v[a].push_back({b,-c});
        //v[b].push_back({a,-c});
    }
    priority_queue<pair<int,int>> q;
    int visitato[MAXN];
    int distanze[MAXN];
    for(int i=0;i<nodi;i++){
        visitato[i]=0;
        distanze[i]=-1e9;
    }
    distanze[nodoiniziale]=0;
    q.push({0,nodoiniziale});
    int corrente=nodoiniziale;
    while (q.size()!=0 && corrente!=nododaraggiungere){ // non ||
        corrente= q.top().second; 
	
        q.pop();
        if (visitato[corrente]==0){
            visitato[corrente] = 1;
            for (auto w : v[corrente]) {
                if (distanze[corrente]+w.second> distanze[w.first]) {
                    distanze[w.first] = distanze[corrente]+w.second;
                    q.push({distanze[w.first],w.first});
                }
            }
        }
    }
    ou<<-distanze[nododaraggiungere];
    return 0;
}

```

Per il 100/100 passare alle variabili long long come già detto

[Pagina precedente](https://forum.olinfo.it/t/2-problemi-nellimplementazione-dijkstra/5490.md?page=1)