Olá meus amigos nerds, hoje vamos ajudar Juquinha a decidir quais cidades ele pode visitar. Já que é isso que o problema 819. Pedágio nos pede para fazer. Mais especificamente, dado um mapa com as cidades e estradas, determinar quais cidades são alcançáveis a partir da cidade em que Juquinha se encontra e que o caminho até elas necessite que sejam pagos no máximo P pedágios.
Solução
O problema quase que implora por uma solução usando-se grafos, onde os vértices representam cidades e as arestas rodovias entre elas. Neste grafo o peso de uma aresta representa o custo do pedágio. Assim sendo o problema se reduz ao cálculo do caminho mínimo entre o vértice que representa a cidade onde Juquinha está e todos os outros vértices do grafo.
O caminho mínimo pode ser calculado facilmente usando-se o algoritmo de dijkstra. Hoje estou com pouco tempo, mas outro dia eu ainda quero discutir mais esse, que é um algoritmo muito clássico.
Assim sendo, para resolver o problema basta calcular o caminho mínimo e a resposta será o conjunto de cidades que estão a menos de P pedágios de distância.
P.S. como todos os pesos das arestas são iguais a 1 eu poderia ter simplesmente feito uma busca em largura para calcular a distância, mas resolvi usar dijkstra para deixar a explicação da solução mais simples :).
Implementação
P.S. Não reparem a feiura do código, mas é que eu resolvi esse problema faz muitos anos e fiquei com preguiça de deixar o código mais bonitinho. Pelo menos, observem que realmente melhoramos quando brincamos continuamente de resolver problemas kkk.
Tentando resolver com este código:
ResponderExcluir#include
#include
#include
#define MAX 50
int matriz[MAX][MAX], atingiveis[MAX], cidades, estradas, localizacao, numPedagios;
void preencherMatriz(){
int i, cidadeUm, cidadeDois;
for(i=0;i numPedagios){
return;
}
else if(cidadeAtual != localizacao-1){
atingiveis[cidadeAtual] = cidadeAtual+1;
}
int i;
for(i=0;i 0){
printf("%d ",atingiveis[i]);
}
i++;
}
printf("\n\n");
memset(atingiveis,0,sizeof(atingiveis));
memset(matriz,0,sizeof(matriz));
teste++;
}
return 0;
}
Mas está dando resposta errada. Para os dois exemplos de entrada, o código funciona, tem ideia do que esteja dando errado?
Qual a sua ideia para resolver o problema?
ResponderExcluirAcho que vc não colocou o código todo. Tem um else ali no inicio sem if :p
Coloca o código certinho ai que a gente debuga :)
Este comentário foi removido pelo autor.
ResponderExcluirDeu pau pra enviar...
ResponderExcluirA ideia é preencher a matriz de adjacências, sem mistério, 1 tem estrada e 0 não.
no main eu chamo após o preenchimento da matriz:
acharCidadesAtingiveis(localizacao-1,0)
obs: localizacao -1 pois a cidade 1, por exemplo, tem o índice 0.
void acharCidadesAtingiveis(int cidadeAtual, int distanciaPercorrida){
if(distanciaPercorrida > numPedagios){
return;
}
else if(cidadeAtual != localizacao-1){
atingiveis[cidadeAtual] = cidadeAtual+1;
}
int i;
for(i=0;i<cidades;i++){
if(matriz[cidadeAtual][i] == 1 && atingiveis[i] == 0 && i != localizacao -1){
acharCidadesAtingiveis(i,distanciaPercorrida+1);
}
}
}
1ª instância tem:
cidadeAtual = linha correspondente na matriz
distanciaPercorrida = 0 (como veio do main, junto com a cidade inicial)
atingiveis[50] com tudo 0 a princípio. Neste cursor eu não preencho a distância, como no dijkstra, se ele tiver um número maior que zero, significa que este número é a cidade atingivel. atingiveis[0] = 1, significa que 1 é atingivel, pela restrição dos pedágios.
retorno quando a distância supera o limite, e não checo os vizinho duas vezes, de quem já tiver sido considerado atingivel. Fiz isto para ganhar performance, pois não preciso saber a distância minima entre todos os vertices, em relação a origem. Mas quais são atingiveis em X pedágios.
Acho que entendi sua ideia. Note que pode haver mais de um caminho ligando a cidade atual a uma cidade qualquer, assim não basta uma busca em profundidade como vc fez, tem que saber de todos os caminhos que ligam um par de cidades qual é o menor, seja atravez de uma busca em largura ou algum algoritmo de caminho mínimo (na solução eu usei dijkstra).
ExcluirTalvez enviando separado dê certo:
ResponderExcluirint main(){
memset(atingiveis,0,sizeof(atingiveis));
int teste = 1, result, i;
while(1){
scanf("%d%d%d%d", &cidades, &estradas, &localizacao, &numPedagios);
if(cidades==0 && estradas==0 && localizacao==0 && numPedagios==0)
return 0;
preencherMatriz();
acharCidadesAtingiveis(localizacao-1,0);
printf("Teste %d\n",teste);
i=0;
while(i 0){
printf("%d ",atingiveis[i]);
}
i++;
}
printf("\n\n");
memset(atingiveis,0,sizeof(atingiveis));
memset(matriz,0,sizeof(matriz));
teste++;
}
return 0;
}
Tentei ver se não era identação da saída, criei várias entradas para testar manualmente, não encontrei erro algum.
PS: rodei seu código no spoj e deu erro de compilação. Meu codeblocks aceita numa boa... no spoj falha.
ResponderExcluirEstranho esse é o mesmo código que está como AC na minha conta do spoj. Vc testou com qual versão do c++ disponível lá?
Excluir
ResponderExcluir#include
#include
#include
#define MAX 50
int matriz[MAX][MAX], atingiveis[MAX], cidades, estradas, localizacao, numPedagios;
void preencherMatriz(){
int i, cidadeUm, cidadeDois;
for(i=0;i<estradas;i++){
scanf("%d%d",&cidadeUm, &cidadeDois);
matriz[cidadeUm-1][cidadeDois-1] = 1;
matriz[cidadeDois-1][cidadeUm-1] = 1;
}
}
restante...