Categoria: Grafos (DFS)

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