Buonasera stavo svolgendo il problema bus trip solo che nonostante il codice sembra funzionare per tutte le testcase ed anche in tempo abbastanza ragionevole continua a fallire solo la numero 7, se qualcuno mi può dare un consiglio su come risolvere o passarmi un input per il quale non funziona in modo da correggerlo gliene sarei grato,
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#define INF 1e9
struct Edge {
long int des, oPartenza,oArrivo;
};
int main() {
std::ifstream cin("input.txt");
std::ofstream cout("output.txt");
long int N, M, Start, Target,src;
cin >> N;
cin >> Start >> Target;
cin >> M;
std::vector<Edge> edges[N];
std::priority_queue<std::pair< int, int>> q;
bool processed[N] = {false};
for ( int i = 0; i < M; i++)
{
Edge edge;
cin >> src >> edge.oPartenza >> edge.des >> edge.oArrivo;
edges[src].push_back(edge);
}
long int distance[N];
for(int i = 0; i < N; i++)
{
distance[i] = INF;
}
long int max = -1;
long int bus[N] = {0};
distance[Start] = 0;
q.push({0, Start});
while (!q.empty())
{
int nodo = q.top().second;
q.pop();
if (processed[nodo]) continue;
processed[nodo] = true;
for (auto u : edges[nodo])
{
if (!processed[u.des] && distance[nodo] <= u.oPartenza && u.oArrivo <= distance[u.des])
{
distance[u.des] = u.oArrivo;
if(u.des!=Target)
{
bus[u.des] = bus[nodo] + 1;
}
q.push({-distance[u.des], u.des});
}
if(u.des == Target && distance[nodo] <= u.oPartenza && bus[nodo] + 1 > bus[u.des])
{
bus[u.des] = bus[nodo] + 1;
max = distance[u.des];
}
}
}
if(processed[Target])
{
cout << max << std::endl;
}
else
{
cout << "IMPOSSIBLE" << std::endl;
}
return 0;
}