TOPIC

PROBLEM 1123 - URI Fórum 1.0

URI Online Judge asked 7 years ago

URI Online Judge Fórum 1.0

MOD

This topic was solved and cannot recieve new replies.

  • Gabriel Moreira de Oliveira replied 3 years ago

    Olá, estou utilizando uma matriz de adjacências para representar o grafo deste problema e o algoritmo de Dijkstra para encontrar o caminho mínimo. Meu problema é com a restrição. Alguém tem alguma dica para me dar? Lembrando que estou utilizando matriz de adjacências. Obrigado!

  • João replied 4 years ago

    Um Dijkstra resolve, basta pensar no seguinte: Cada vértice V ou faz parte da rota de serviço, ou não. Se ele for parte da rota, você coloca o vértice V+1 com um custo dist[V][V+1] (tem que ir de V para V+1 obrigatoriamente) na fila de prioridade (desde que V não seja o destino). Se não for, você olha todos os vizinhos dele normalmente. Um if dentro do Dijkstra da certo.

  • André Luiz Bittencourt replied 4 years ago

    Alguem pode dar uma ideia de como resolver esse problema por favor....

  • Welton Cardoso replied 7 years ago

    Olá Samuel Chagas,

    Se você não tiver passado ele ainda, acabei de resolve-lo com uma DP, meu estado foi o museu que estou, uma mascara para saber quais museus já visitei, o tempo gasto e a quantidade de museus visitados até o momento. Tem uma sacada para conseguir passar no tempo, tenta pensar no pior caso quando n == 20 ( no que você postou é 8, mas não encontrei o site que tinha 8, apenas 20). Creio que no Live Archive tenha mais casos de testes que nos outros sites, pois minha primeira versão passou nos outros e deu WA nele.

  • José Luís Rodrigues Terceiro replied 7 years ago

    Acho que essa sua pergunta vai ser excluída, mas mesmo assim ... Esse prolema noite no museu, quanto a guloso eu não sei, mas como n=8 dá pra fazer com backtrack, testando todas as permutações de museus. Até porque acho que não tem algoritmo mais eficiente já que esse problema parece ser adaptado do problema caixeiro viajante.

  • Samuel Chagas replied 7 years ago

    Boa noite pessoal! Sei que aqui é o tópico pro problema 1123, mas meu problema é outro. Estou com dificuldade num problema aqui e queria saber se alguém tem alguma dica de como fazer. Segue o problema:

    Noite no Museu

    A cidade de Viena é chamada “cidade da cultura“ porque, entre outras coisas, abriga uma grande quantidade de museus, mais de 100. Como conseqüência, é muito difícil e caro visitar todos os museus, não importando o tempo que ficar na cidade. Entretanto, tem uma noite especial, chamada “Noite no Museu”, que se permite a visita a vários museus com apenas um ingresso, das 18:00h até a 01:00h da manhã do próximo dia. Porém, é impossível visitar todos os museus da cidade por duas razões principais. A primeira razão é que alguns museus em Viena não entram nessa promoção porque fecham às 17:00 h. A segunda razão é que não há tempo suficiente para visitar os museus no tempo de 7 horas. Sua tarefa é construir um programa que dado o número de museus participantes, o tempo necessário para visitar cada museu e o tempo que leva para ir de um museu ao outro, encontre o melhor “tour” para os visitantes, ou seja, visitar o maior número de museus nessa noite.

    Entrada

    A entrada contém vários casos de testes. A primeira linha de um caso de teste contém um inteiro N, que indicará o número de museus participantes na promoção ( 1 <= N <= 8). Cada museu tem um identificador único variando de 1 a N. A segunda linha contém N inteiros indicando o tempo, em minutos, necessário para visitar cada museu, de 1 a N. Então, teremos mais n linhas descrevendo o tempo para ir de um museu para todos os outros. A i-ésima linha contém N inteiros Mk ( 1 <= k <= N) representando o tempo, em minutos, para ir de um museu i para um museu k. Assuma que o i-ésimo inteiro na i-ésima linha é igual a 0. O final da entrada é indicado por N=0.

    Saída

    Para cada caso de teste, seu programa deverá produzir uma linha contendo o número máximo de museus que podem ser visitados durante a noite.

    Exemplo 2 500 500 0 120 200 0 2 220 220 0 30 20 0 2 150 150 0 120 200 0 0

    Saída para o exemplo 0 1 2

    Pensei em uma solução gulosa já que o máximo de N é 8. Vou começar a implementa-la aqui agora. Mas aguardo dicas!