TOPIC

PROBLEM 1711 - URI Fórum 1.0

URI Online Judge asked 6 years ago

URI Online Judge Fórum 1.0

MOD

This topic was solved and cannot recieve new replies.

  • Altamir Gomes Bispo Junior replied 5 years ago

    O percurso deve completar um ciclo pelo menos uma vez (observe que é impossível de voltar ao início se não houver nenhum ciclo no grafo com tamanho igual a ou maior que o comprimento de Dona Minhoca). Outra observação é a de que o caminho até o vértice de interseção com algum ciclo deve ser um caminho mínimo. Portanto, o caminho de volta deverá ter a mesma distância (mínima) daquele de ida.

    É interessante anotar quais arestas pertencem aos ciclos ou quais não pertencem. Para isso, há algoritmos como o encontra-pontes do Tarjan e a decomposição em cadeias do grafo.

  • Unknown replied 4 years ago

    Well, i got AC with 0.272. What i did: find all bridges with tarjan algorithm, run DFS on every vertex to find the cycles which each one belongs, and then dijkstra for every query of the question.

  • Im Olek replied 5 years ago

    I got AC but I wanted to understand, my time is 0.9, ie was close. My strategy is to mark the cycles with DFS and then a SSSP for all vertices each query. and choose the best.

    I saw that some have gone under 0.1. Any tips? thanks

  • Wadson Barbosa replied 5 years ago

    Há algum caso de teste especial? estou levando 10% WA, poderia me mandar algum caso de teste?

  • Railton Thales replied 5 years ago

    Alguma dica para esse problema?