Ho provato a svolgere il problema “Bus Trip” utilizzando l’algoritmo di Dijkstra. Tutto va bene nei primi 3 test case ma nel quarto e nel quinto alcuni output vengono segnati come errati. Potreste darmi una mano?
Lascio qui sotto la mia soluzione e in allegato un immagine dei test case 4 e 5.
Grazie in anticipo.
#include <iostream>
#include <vector>
#include <set>
struct busTrip{
int arrive, tStart, tArrive;
};
int Dijkstra(std::vector <std::vector <busTrip>> &bus, int start, int arrive){
std::vector <bool> visited (bus.size());
std::vector <int> weight (bus.size(), -1);
std::set <int> coda;
weight[start] = 0;
coda.insert(start);
while(!coda.empty()){
int current = *coda.begin();
if(current == arrive)
break;
visited[current] = true;
coda.erase(coda.begin());
for(auto trip : bus[current]){
if(!visited[trip.arrive] && weight[current] <= trip.tStart && (weight[trip.arrive] == -1 || trip.tArrive < weight[trip.arrive])){
weight[trip.arrive] = trip.tArrive;
coda.insert(trip.arrive);
}
}
}
return weight[arrive];
}
int main(){
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int N, S, E, M;
std::cin >> N >> S >> E >> M;
std::vector <std::vector <busTrip>> bus (N);
for(int i = 0; i < M; i++){
int start;
busTrip trip;
std::cin >> start >> trip.tStart >> trip.arrive >> trip.tArrive;
bus[start].push_back(trip);
}
int result = Dijkstra(bus, S, E);
if(result == -1)
std::cout << "IMPOSSIBLE";
else
std::cout << result;
}
