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:
#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;
}