ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1004. Sightseeing Trip

How to deal with this problem?
Posted by pyh119 10 Dec 2006 19:49
I can not solve it,please tell me how to solve it,thank you!^_^
Re: How to deal with this problem?
Posted by KIRILL(ArcSTU) 10 Dec 2006 20:39
You can do this for all edges:
1 - delete edge
2 - find shortest way (Deikstra) between 2 vertex, which
are connetcted with this edge
3 - insert edge
 This solution (O(N^4))pass time limits

P.S.
It may done in N^3 with Deikstra for each vertex
I don't know how to do this :(
Re: How to deal with this problem?
Posted by yzthz 17 Mar 2009 07:37
Is there anything to do with Hamiltonian circuit ?
Re: How to deal with this problem?
Posted by Roman Rubanenko 9 Apr 2010 22:26
Hamiltonian circuit for n=100 ?!?!?!
We will die before your program will give us an answer :O
Re: How to deal with this problem?
Posted by ile 10 Apr 2010 01:11
Well... it's not always true that Hamiltonian related problems are NP completed.

You can always use some heuristics that will reduce it to polynomial time...

so don't be so marked ^^
Re: How to deal with this problem?
Posted by beta 20 Dec 2012 19:56
Re: How to deal with this problem?
Posted by begi 27 Nov 2014 11:43
Thank you for the hint.