# Problema sentieri bollenti

**URL:** <https://forum.olinfo.it/t/problema-sentieri-bollenti/4393>\
**Category:** Aiuto\
**Created:** [8 Febbraio 2017, 4:52pm UTC](https://forum.olinfo.it/t/problema-sentieri-bollenti/4393 "2017-02-08T16:52:15Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![Keyword](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/k/ebca7d/32.png) [@Keyword](https://forum.olinfo.it/u/Keyword)\
**Post date:** [8 Febbraio 2017, 4:52pm UTC](https://forum.olinfo.it/t/problema-sentieri-bollenti/4393/1 "2017-02-08T16:52:15Z")

</div>

Non capisco il motivo, ma non mi da nemmeno un caso giusto, cosa improbabile, in quanto ho provato su diversi grafi e mi ha sempre dato un output corrispondente.  
Non so se l’algoritmo sia giusto, ma i casi base mi vanno tranquillamente, in più ho provato a costruire alcuni grafi con casi particolari e mi va.  
Ecco il codice:

```auto
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <limits>
#define MAXN 101
#define MAXM 1001
using namespace std;

int N,A,B;
vector<int> graph[MAXN];
vector<int> graph1[MAXN];
bool visited[MAXN];
int dist[MAXN];

int ultimo;
void bfs(int sorgente)
{
    queue<int>coda;
    coda.push(sorgente);
    while(!coda.empty())
    {
        int corrente = coda.front();
        coda.pop();
        if(visited[corrente] == false)
        {
            visited[corrente] = true;
           // cout<<corrente<<endl;
            for(int i = 0;i<graph[corrente].size();i++)
            {
                coda.push(graph[corrente][i]);
            }
            ultimo = corrente;
        }
    }

}
void bfs1(int sorgente,int* res)
{
    queue<pair<int,int> >coda;
    coda.push(make_pair(sorgente,0));
    for(int i = 1;i<=N;i++)
    {
        visited[i] = false;
    }
    while(!coda.empty())
    {
        pair<int,int> corrente = coda.front();
        coda.pop();
        if(visited[corrente.first]) continue;
        visited[corrente.first] = true;
        res[corrente.first] = corrente.second;

        //cout<<corrente.first<<endl;

        for(unsigned i = 0;i<graph1[corrente.first].size();i++)
            coda.push(make_pair(graph1[corrente.first][i],corrente.second+1));
    }
}
int main()
{
    ifstream in("input.txt");
    ofstream out("output.txt");

    in>>N>>A>>B;
    for(int i = 1;i<=N;i++)
    {
        visited[i] = false;
        dist[i] = numeric_limits<int>::max();
    }
    for(int i = 1;i<=A;i++)
    {
        int da,a;
        in>>da>>a;
        graph[da].push_back(a);
        graph[a].push_back(da);
    }
    for(int i = 1;i<=B;i++)
    {
        int da,a;
        in>>da>>a;
        graph1[da].push_back(a);
        graph1[a].push_back(da);
    }
    bfs(1);
    bfs1(N,dist);
    //cout<<ultimo<<endl;
    if(B>0)
        cout<<dist[ultimo];
    else cout<<0;
    return 0;
}

```

---

<div class="post-metadata">

**Author:** ![erolm\_a](https://forum.olinfo.it/user_avatar/forum.olinfo.it/erolm_a/32/514_2.png) [@erolm\_a](https://forum.olinfo.it/u/erolm_a)\
**Post date:** [8 Febbraio 2017, 8:19pm UTC](https://forum.olinfo.it/t/problema-sentieri-bollenti/4393/2 "2017-02-08T20:19:41Z")

</div>

Perché 2 BFS? Una già basta, se opportunamente modificata.

Puoi risolverla in due modi. Il primo, come ho detto, è una BFS modificata, chiamata “0-1 BFS”, il secondo è il classico Dijkstra (ma la complessità è maggiore)