KAN13B - Editorial

PROBLEM LINK:

Practice
Contest

Author: Tanaeem Moosa
Tester: Jingbo Shang
Editorialist: Jingbo Shang

DIFFICULTY:

Medium

PREREQUISITES:

Dijkstra, Binary Heap

PROBLEM:

Given a R×C matrix and the definition of the distance, you need to answer Q queries of the shortest distance between two nodes.

EXPLANATION:

First of all, if we directly use Dijkstra to calculate the shortest distance, the time complexity is O(QR^2 C^2 ).

Secondly, we should observe that only two adjacent entries have edges. Therefore, there are only O(RC) edges in total.

Combining these two together, we can using Binary Heap to optimize the time complexity of Dijkstra to O(QRC logRC).

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

@shangjingbo :diamonds::diamonds: @admin where can i find a link to author’s and tester’s solution… please help?

//