|
|
back to boardIt's a good problem ! Posted by hello 25 Jun 2004 19:03 Re: It's a good problem ! Posted by svr 4 Feb 2007 11:27 One of solvable by Dijksta with heap.
But interesting how to speed up.
Idea: use struct (int,int*sqrt(2)) instead of double
for distances with compair: (h1,h2*sqrt(2))<(q1,q2*sqrt(2))~
(h1-q1)^2<2*(h2-q2)^2 in int type. Re: It's a good problem ! i have used other method, and i have best AC 0.265 sec 220 kb Re: It's a good problem ! One of solvable by Dijksta with heap.
But interesting how to speed up.
Idea: use struct (int,int*sqrt(2)) instead of double
for distances with compair: (h1,h2*sqrt(2))<(q1,q2*sqrt(2))~
(h1-q1)^2<2*(h2-q2)^2 in int type. I have read you massage and after wrote as you said. I got TLE. I changed <<<struct harT{long k1, k2;};>>> on <<<double>>> and get AC. Conclusion: It's not good idea or I don't undestand you. =) Edited by author 22.12.2011 03:53 Edited by author 22.12.2011 03:54 |
|
|
