Обсуждение @ 1119. Метро @ Timus Online Judge

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

Послано Alex Stoff 14 май 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?

Послано Burunduk1 14 май 2006 23:13

Dijkstra.
Vertices - quarters that can be crossed diagonally.

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

Послано Alex Stoff 15 май 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?

Послано Burunduk1 15 май 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?

Послано Alex Stoff 15 май 2006 20:53

Thanks. AC now.

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

Послано CmYkRgB123 31 окт 2008 17:44

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

Послано Georgi_georgiev 4 июн 2009 17:54

Longest increasing subsequence

Обсуждение задачи 1119. Метро