Explicações teóricas sobre Grafos aqui
Resumo: Dado a origem, determinar a distância máxima que pode ser alcançada
Explicação: Nos comentários temos a explicação detalhada de cada passo. Mas de forma geral, vamos realizar uma busca em largura (BFS), partindo da origem e a cada passo vamos marcando na matriz de enfileiramento que aquela cidade já está na fila daquele dia.
Dessa maneira conseguimos determinar se é possível ou não chegar ao destino.
Obs: BFS significa Breadth First Search (Busca Primeiro em Largura).
Vamos ao código:
//Autor: Filipe Areias Névola
//Ano: 2008
//Licensa: Você pode usar e alterar, mas deve manter o Autor
#include <stdio.h> //Biblioteca padrão de entrada e saída
#include <string.h>
#define NMAX 101
#define MAXD 201
//matriz de adjâcencia
short g[NMAX][NMAX];
int dias[NMAX*MAXD];//cada dia esta em que ponto do caminho
int fila[NMAX*MAXD];
int enf[MAXD][MAXD];//marcacao dos enfileirados
int o,d,dia;
int n;
int main(){
int m,i,j,x,y,v;
int fim,ini;
bool pode;
while(scanf("%d %d",&n,&m)==2&&n){
//o grafo está zerado
memset(g,0,sizeof(g));
//não tem nada enfileirado
memset(enf,0,sizeof(enf));
//todas não foram visitadas
memset(dias,-1, sizeof(dias));
for(i=0;i<m;++i){
scanf("%d %d",&x,&y);
//grafo bidirecional, marca pros 2 lados
g[x][y]=g[y][x]=1;
}
//lê origem, destino e número de dias
scanf("%d %d %d",&o,&d,&dia);
pode=false;
/**CASO ESPECIAL, QNDO NÚMERO DE DIAS É 0(ZERO)**/
if(dia==0){//em nenhum dia nao sai da cidade
if(o==d)//se a origem é igual ao destino
pode=true;//viagem ideal
//se origem é diferente do destino viagem nao é ideal pois nao ira mudar d cidade
}
/**CASO COMUM**/
else{
fim=1;//fim da fila
ini=0;//inicio da fila
fila[0]=o;//posicao inicial da fila é a cidade de origem
dias[0]=0;//dia 0
while(ini<fim && dias[ini]<dia){//enqto o dia atual é menor que o dia IDEAL
v=fila[ini];//tira da fila
for(i=1;i<=n;++i){//roda os vertices
if(g[v][i] && !enf[i][dias[ini]+1]){//existe a aresta e este vertice ainda nao
//está na fila do proximo dia
fila[fim]=i;//poe na fila
dias[fim]=dias[ini]+1;//aumenta um dia
enf[i][dias[fim]]=1;//o vertice esta na fila
if(dias[fim]==dia && i==d){//se chegou no dia IDEAL e o vertice é o destino
ini=fim=0;//esvazia a fila
pode=true;//viagem como teobaldo desejava
break;
}
fim++;//aumenta tamanho da fila
}
}
ini++;//proximo vertice da fila
}
}
if(pode)
printf("Yes, Teobaldo can travel.\n");
else
printf("No, Teobaldo can not travel.\n");
}
}Alguma dúvida? Pergunte através dos comentários!A viagem de Teobaldo - SPOJ - 1818 Teobaldo
