ho implementato il codice per risolvere police 5 con l’algoritmo di dijkstra leggermente modificato per le esigenze del problema, ma ottengo in molti testcase output non corretto e non riesco a capire l’errore nel codice.
il mio codice:
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <climits>
using namespace std;
int N, M, T;
vector<int> A, B, C, E;
int mincammino() {
vector<vector<vector<int>>>grafo(N);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
vector<int>D(N);
D.assign(N, -1);
for (int i = 0; i<M; i++) {
grafo[A[i]].push_back({B[i], C[i], E[i]});
grafo[B[i]].push_back({A[i], C[i], E[i]});
}
q.push(make_pair(0, 0));
while (!q.empty()) {
pair<int, int> nodo = q.top();
q.pop();
if ((D[nodo.second] != -1 && nodo.first >= D[nodo.second])) {
continue;
}
D[nodo.second] = nodo.first;
for (const vector<int> &son : grafo[nodo.second]) {
int dis = nodo.first + son[1];
if (son[2] == 1 && dis > T) {
continue;
}
if ((D[son[0]] == -1 || D[son[0]] > dis)) {
q.push(make_pair(dis, son[0]));
}
}
}
int min = D[D.size()-1];
return min;
}
int main() {
cin >> N >> M >> T;
A.resize(M);
B.resize(M);
C.resize(M);
E.resize(M);
for (int i = 0; i < M; i++) {
cin >> A[i] >> B[i] >> C[i] >> E[i];
}
cout << mincammino() << endl; // stampa il risultato
return 0;
}