I'm trying to generate a testcase so that Prim with complexity $$$O(N^2)$$$ is significantly faster than Prim with priority queue $$$O((N + M)log(N + M)$$$ (Here $$$N$$$ is number of vertices and $$$M$$$ is number of edges).

However as I generate with random weight of the edges the two algorithm runs with nearly the same amount of time (I generate with $$$N = 2500$$$ and $$$M = N * (N - 1) / 2$$$ (As polygon doesn't allow bigger constraint)).

I wonder if there is a way to construct such test (that for example, the priority queue contains many elements while running...).

Thanks.

Are you able to provide the source code of your implementations? I suspect that you did not implement the first version correctly.

https://ideone.com/6O6oxw

This is the $$$O(N^2)$$$ version. The problem is to find the total weight of Minimum Spanning Tree.

Reading the input is slower than other standard operations. If the input size is $$$M$$$, you can assume that reading the input is $$$O(M \cdot \log M)$$$. With this assumption, you're trying to distinguish between two algorithms with same time complexity.

Try a compressed input like:

Thanks <3

pls let me get a new haircut

http://usaco.org/index.php?page=viewproblem2&cpid=946

This problem forced $$$\mathcal O(N^2)$$$ Prim's by setting $$$N \leq 7500$$$ and using an alternative scheme for generating the edge weights to get around input bottleneck. If you take this approach, make sure you pick a better edge weight function because this particular function allowed unintended $$$\mathcal O(1)$$$ solutions.

Thanks so much!

Unrelated, but how

doyou solve this in $$$\mathcal{O}(1)$$$?https://usaco.guide/problems/usaco-946-i-would-walk-500-miles/solution

See solution 3

You can drive vertexes into 2 groups, and have small weights inside each one, and big weights from one to another.