Police Investigation 5 - 10/100

Aiuto
1

Sto cercando di risolvere questo problema da un po’ ma non riesco a superare il 10/100 e non trovo l’errore, qualcuno può aiutarmi?
questo è il mio codice:

#include <iostream>
#include <bits/stdc++.h>
#define MAXN 10000
#define MAXT 100000000

using namespace std;

ifstream fin ("input.txt");
ofstream fout ("output.txt");

//adj.first= dove porta la strada 
//adj.second= quanto tempo costa andarci
//esplode[nodo dove siamo][nodo dove andremo]= se può esplodere questa strada

list<pair<int,int>>adj[MAXN];
vector<bool>visited(MAXN);  
int esplode[MAXN][MAXN]; //quelli che esploderanno
long long soluzione=-1;


void dps(long long x,long long tempoFinora,long long& T,long long& N){
    
    //se non visitato
    if(!visited[x])
    {
        //lo visita
        visited[x]=true;
        
        //se non è la fine
        if(x!=N-1)
        {
            //per ogni strada
        for(auto u: adj[x])
        {
            
            //se esploderà
            if(esplode[x][u.first]==1 && T<tempoFinora+ u.second)
            {
                //non ci andare
            }else //se non esploderà
            {
                //visitalo
              dps(u.first,tempoFinora+u.second,T,N);
            }
        }
        }else //se era l'obiettivo
        {
            //aggiorna la soluzione
            if (tempoFinora<soluzione || soluzione==-1)
            {
                soluzione=tempoFinora; 
            }
                
           
        }
    }


}




int main()
{
    //input
    long long N,M,T;
    fin>>N>>M>>T;

    long long legare1,legare2,peso,seEsplode;
    for(long long i=0;i<M;i++)
    {

        fin>>legare1>>legare2>>peso>>seEsplode;
        adj[legare1].push_back(make_pair(legare2,peso));

        esplode[legare1][legare2]=seEsplode;

    }

    dps(0,0,T,N);

    fout<<soluzione<<endl;
}
2

Non è detto che quando segni come visitato un nodo effettivamente tu abbia trovato il percorso migliore da 0 a quel nodo.

      300
  (1) --> (2)
   |       ^
 2 |       | 2
   v       |
  (3) --> (4)
       2

Per esempio in questo grafo il percorso migliore da 1 a 2 non è quello diretto ma 1->3->4->2.
Questo problema si risolve adattando l’algoritmo di dijkstra; nella sezione grafi di algobadge dovresti trovare delle dispense che ne spiegano il funzionamento.