Teoria dos Grafos - Uma Jornada Final na Grafolândia: Desafio de Percursos Mínimos em C

Painel Meus cursos 2023Q3TG Entrega 4 práticos 13dezembro Uma Jornada Final na Grafolândia 2023 Q3 MCTA02717 Teoria dos Grafos Descrição Enviar Editar Visualizar envios Uma Jornada Final na Grafolândia Data de entrega quinta 14 Dez 2023 0100 Número máximo de arquivos 1 Tipo de trabalho Trabalho individual A Grafolândia agora plenamente restaurada e envolta em seu esplendor mágico abrese diante de seus habitantes com promessas inexploradas e oportunidades cintilantes As estradas marcadas por suas propriedades únicas persistem como trilhas de avanço tecendo um labirinto fascinante de conexões unidirecionais Os habitantes mergulhados em uma era de paz e harmonia anseiam por explorar e percorrer os encantos da Grafolândia Cientes de suas próprias finanças aspiram a desbravar a terra mágica realizando ocasionais mochilões o que significa que querem absorver as maravilhas de sua terra ao máximo mas com gastos mínimos Isso também significa que infelizmente alguns povoados serão inalcançáveis pois só seria possível chegar até eles de avião Sua nobre missão é orientar os habitantes na criação das jornadas mais eficientes pela Grafolândia utilizando sabiamente as vias encantadas Dada a localização atual de um habitante seu desafio é descobrir quais são os menores percursos que ele pode fazer para qualquer outro povoado Instruções Independente dos resultados dos testes o não cumprimento dos critérios abaixo implicará em nota zero para esta atividade Qualquer dúvida entre em contato Você deve resolver esse problema em linguagem C usando grafosdigrafos que devem ser representados por listas de adjacências Você deve incluir no início do seu programa uma breve cabeçalho contendo no mínimo o seu nome e RA Se você precisar implementar uma busca em largura você precisa implementar uma estrutura de dados Fila Se você precisar implementar o algoritmo de Kruskal você precisa implementar uma estrutura de dados UnionFind Use o algoritmo de ordenação disponível no material de aula Se você precisar implementar o algoritmo de Prim você precisa implementar uma estrutura de dados Heap Se você precisar implementar o algoritmo de Tarjan você precisa implementar uma estrutura de dados Pilha Se você precisar implementar o algoritmo de Dijkstra você precisa implementar uma estrutura de dados Heap Se você precisar implementar o algoritmo de Hierholzer você precisa implementar uma estrutura de dados Pilha Indente corretamente o seu código e inclua comentários necessários no decorrer do seu programa Entrada A primeira linha da entrada consiste de dois inteiros V e E separados por espaço onde 1 V 1000 e 0 E VV 1 representando o número de povoados e o número de estradas da Grafolândia respectivamente Cada povoado é representado por um código numérico entre 0 e V 1 A próxima linha consiste de um único inteiro s indicando o povoado do habitante que precisa de ajuda Cada uma das próximas E linhas consiste de um trio de números separados por espaços sendo dois inteiros x y e um número real w onde 0 x y V 1 e 0 w 500 que indicam que há uma estrada mágica do povoado x para o povoado y e cujo custo de percurso é w Saída Seu programa deve imprimir exatamente V linhas sendo uma para cada povoado da Grafolândia Na iésima linha imprima si perc se for possível ir até o povoado i substituindo perc pelo menor percurso de s até i que consiste de uma sequência de povoados separados por espaço o habitante precisa saber como chegar até i si impossivel se não for possível ir de mochilão de s até o povoado i si o mais barato eh ficar em casa se i s Atenção o percurso para o povoado i precisa ser impresso antes do percurso para o povoado j se i j Exemplos Teste 1 Entrada 8 12 5 1 0 9 1 3 9 2 1 4 2 5 3 2 4 3 3 1 2 3 7 2 3 5 7 4 2 6 4 6 7 5 1 6 6 7 5 Única saída 50 5 1 0 51 5 1 52 impossivel 53 5 1 3 54 impossivel 55 o mais barato eh ficar em casa 56 impossivel 57 5 1 3 7 Teste 2 Entrada 8 12 4 1 0 9 1 3 9 2 1 4 2 5 3 2 4 3 3 1 2 3 7 2 3 5 7 4 2 6 4 6 7 5 1 6 6 7 5 Única saída 40 4 2 1 0 41 4 2 1 42 4 2 43 4 2 1 3 44 o mais barato eh ficar em casa 45 4 2 5 46 4 6 47 4 6 7 Teste 3 Entrada 8 12 6 1 0 9 1 3 9 2 1 4 2 5 3 2 4 3 3 1 2 3 7 2 3 5 7 4 2 6 4 6 7 5 1 6 6 7 5 Única saída VPL 60 impossivel 61 impossivel 62 impossivel 63 impossivel 64 impossivel 65 impossivel 66 o mais barato eh ficar em casa 67 6 7 Teste 4 Entrada 5 7 4 0 2 147157803960143 1 2 944111885495974 1 3 186479675741142 1 4 231926045021029 2 3 179004480061572 2 4 276148224952772 3 4 657337868609623 Única saída 40 impossivel 41 impossivel 42 impossivel 43 impossivel 44 o mais barato eh ficar em casa Universidade Federal do ABC Moodle 2023 Obter o aplicativo para dispositivos móveis Lista 6 Seguir para Este é o Ambiente Virtual de Aprendizagem da UFABC para apoio ao ensino presencial e semipresencial Esta plataforma permite que os usuários educadoresalunos possam criar cursos gerenciálos e participar de maneira colaborativa Informação Conheça a UFABC Conheça o NTI Conheça o Netel Contato Av dos Estados 5001 Bairro Bangu Santo André SP Brasil CEP 09210580 Siganos