# Aiuto 80/100 Bus Trip (trip)

**URL:** <https://forum.olinfo.it/t/aiuto-80-100-bus-trip-trip/8562>\
**Category:** Aiuto\
**Created:** [27 Ottobre 2023, 8:13pm UTC](https://forum.olinfo.it/t/aiuto-80-100-bus-trip-trip/8562 "2023-10-27T20:13:55Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![MarcelloDelFior](https://forum.olinfo.it/user_avatar/forum.olinfo.it/marcellodelfior/32/1569_2.png) [@MarcelloDelFior](https://forum.olinfo.it/u/MarcelloDelFior)\
**Post date:** [27 Ottobre 2023, 8:13pm UTC](https://forum.olinfo.it/t/aiuto-80-100-bus-trip-trip/8562/1 "2023-10-27T20:13:55Z")

</div>

Buonasera stavo svolgendo il problema [bus trip](https://training.olinfo.it/#/task/ois_trip/statement) 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,

```auto
#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;
}

```

---

<div class="post-metadata">

**Author:** ![qwfwq](https://forum.olinfo.it/user_avatar/forum.olinfo.it/qwfwq/32/2974_2.png) [@qwfwq](https://forum.olinfo.it/u/qwfwq)\
**Post date:** [28 Ottobre 2023, 5:37am UTC](https://forum.olinfo.it/t/aiuto-80-100-bus-trip-trip/8562/2 "2023-10-28T05:37:07Z")

</div>

Con questo input:

4  
0 3  
5  
0 0 1 4  
1 5 2 6  
0 0 2 1  
1 6 3 7  
2 7 3 8

il codice restituisce 8 mentre il risultato corretto è 7.  
Quando arrivi in una città se ci sono 2 alternative per raggiungere la destinazione finale il programma prende il primo bus che parte anche se non è la scelta migliore.

---

<div class="post-metadata">

**Author:** ![MarcelloDelFior](https://forum.olinfo.it/user_avatar/forum.olinfo.it/marcellodelfior/32/1569_2.png) [@MarcelloDelFior](https://forum.olinfo.it/u/MarcelloDelFior)\
**Post date:** [28 Ottobre 2023, 6:47am UTC](https://forum.olinfo.it/t/aiuto-80-100-bus-trip-trip/8562/3 "2023-10-28T06:47:40Z")

</div>

Avevo sbagliato a leggere la consegna ed avevo letto " using as many as possible " e non " as many as needed ", ti ringrazio