2 problemi nell'implementazione dijkstra


#21

Semplicemente c’è scritto:

Risolvete Dijkstra su un grafo diretto

Buon Natale


#22

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


#23

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


#24

https://pastebin.com/f4CGsQfa 95/100


#25

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 :slight_smile:


#26

Cosa sarebbe MAXP?

Comunque, con cosa sostituisco “1e9”?


#27

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

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 :slight_smile:


#28

“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


#29

Grazie mille: funziona


#30

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>


#31

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

#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