Obra: Resolução de problemas/A node too far
um nó muito distante imagine uma rede com um sistema de transmissão de pacotes pequenas unidades de informação que são enviadas recebidas pela rede várias estações computadores conectadas de maneira que possamos evitar um looping infinito nas retransmissões de pacotes que não chegaram aos seus destinos introduzimos uma regra chamada ttl time to live ttl garante que os pacotes serão perdidos depois de um determinado tempo seria interessante porém que pudéssemos determinar de acordo com as limitações do ttl as estações que não conseguem receber tais pacotes problema node too far aborda exatamente este tema imagine um grafo como da figura seguir se uma mensagem com ttl de for mandada do nó os nós serão alcançados os demais não serão entrada do problema consiste de um número que indica quantidade de conexões entre as estações nós após isso virão as descrições de pares de nós que representam as conexões entre tais nós após as descrições das arestas conexões virá nó de partida dos pacotes apenas número do nó acompanhado do ttl do pacote mais de um caso poderá acontecer para um mesmo grafo ponto de partida para resolução deste problema determinação do tipo ao qual problema pertence este problema um problema de grafos como deu pra ver segundo ponto ser analisado estrutura de dados para armazenarmos nosso grafo por questões de simplicidade usaremos uma matriz de adjacências de dado que só teremos no máximo nós por grafo int matriz vetor citado campo vetor será responsável por setar as posições às quais vão pertencer os nós não atribuiremos os próprios valores dos nós porque como vimos podemos atribuir um rótulo inteiro arbitrário ao nó que pode ser um número muito grande para suportarmos uma gama tão grande de valores precisaríamos de uma matriz de isto como de se supor causaria memory limit exceded também time limit exceded dada complexidade do algoritmo de menor caminho que iremos usar mas como só teremos no máximo nós em cada grafo não precisamos armazenar uma matriz tão grande basta que setemos valores menores para cada nó campo citado irá nos auxiliar nesta tarefa uma vez que cada vez que um nó citado atribuído um valor entre ele para que não venhamos atribuir mais de um valor um mesmo nó verificamos se elemento já foi citado função seguir atribui um infinito cada valor da matriz de adjacências de modo que possamos aplicar nosso algoritmo de menor caminho void infinitza int for função seguir seta todos os valores dos vetores vetor citado no caso do vetor citado em uma determinada posição citadoi indica que elemento ainda não foi citado pela entrada void zera_vetor int for algoritmo de menor caminho que iremos usar de floyd warshall void floyd int for kmatrizik matrizkj matrizij matrizik matrizkj próxima função será chave para resolução do problema ela irá contar quantos nós não serão alcançáveis partir do nó que estaremos analisando ou seja irá verificar quais nós tem um menor caminho para nó que maior que ttl em questão referenciado pela variável ca
ar quais nós tem um menor caminho para nó que maior que ttl em questão referenciado pela variável capacity int conta int node int capacity int counter for icapacity citadoi matriznodei capacity counter return counter seguir temos nossa função principal ela implementa todas as funções que explicamos anteiormente na ordem correta coletando os dados de entrada aplicando os algoritmos certos para dar saída int main int nodes origem destino capacity counter caso while nodes counter infinitza zera_vetor scanf nodes for este problema poderia ser perfeitamente resolvido com uso do algoritmo de dijkstra cuja complexidade n2 menor do que de floyd warshall que n3 uma vez que precisamos apenas do menor caminho de um único nó para todos os outros usamos algoritmo de floyd warshall apenas por sua implementação ser mais simples texto explicativo escrito por samuel lincoln magalhães barrocas