Discussion @ 1119. Metro @ Timus Online Judge

Can U discribe my an idea of O(K^2) solving?

Posted by Alex Stoff 14 May 2006 21:16

Can U discribe my an idea of O(K^2) solving?
Thanks.

Re: Can U discribe my an idea of O(K^2) solving?

Posted by Burunduk1 14 May 2006 23:13

Dijkstra.
Vertices - quarters that can be crossed diagonally.

Re: Can U discribe my an idea of O(K^2) solving?

Posted by Alex Stoff 15 May 2006 18:10

Can U discribe more clearly?
Should I sort diagonalles?
I don't understand the idea... :(

Re: Can U discribe my an idea of O(K^2) solving?

Posted by Burunduk1 15 May 2006 18:27

Two opposite corners of
quarters that can be crossed diagonally and
start and finish positions - vertices.

Edges:
Between any pair of vertices there is
an edge with weight dx+dy.
Also between two opposite corners of a quater -
an edge with weight 1.

In this graph we can (using Dijkstra) find
minimal distance between start and finish.

Re: Can U discribe my an idea of O(K^2) solving?

Posted by Alex Stoff 15 May 2006 20:53

Thanks. AC now.

Re: Can U discribe my an idea of O(K^2) solving?

Posted by CmYkRgB123 31 Oct 2008 17:44

Re: Can U discribe my an idea of O(K^2) solving?

Posted by Georgi_georgiev 4 Jun 2009 17:54

Longest increasing subsequence

Discussion of Problem 1119. Metro