My implementation of Prim's is really slow.

So I searched up a fast way to do Prim's algorithm on geeksforgeeks.com, it is here: http://www.geeksforgeeks.org/greedy-algorithms-set-5-prims-minimum-spanning-tree-mst-2/ It is O(V^2). It uses two disjoint sets and finds the minimum edges between them with an adjacency matrix.

But the website has a faster way: http://www.geeksforgeeks.org/greedy-algorithms-set-5-prims-mst-for-adjacency-list-representation/ It is O(ElogV). It uses an adjacency list and a priority_queue to speed up Prim's.

I understand the concept of Prim's, but my implementation is really slow.

It is O(V^3).

Here is the problem it applies to (very straight forward): http://www.spoj.com/problems/MST/ — I got AC my but my algorithm is very slow

How can I improve this implementation?

I'm writing code that takes in a "maze" and runs bfs. I have already solved it for small test cases, but the code for taking in input fails on large test cases.

Given W (1 <= W <= 38), the width of the maze; H (1 <= H <= 100), the height of the maze; 2*H+1 lines with width 2*W+1 characters that represent the maze in a format like this:

Issue: The loop that takes in the maze stops when i = 19 for the 25x25 maze.

EDIT: Clarification — "taken" will never be printed on the failing test case.

Any ideas what's causing this?

I was going through https://a2oj.com/ codeforces ladders, and I noticed something strange. As I submitted problems in the problem set, I had to wait a bit before I would get a verdict. However, when I opened the contest for the problem, the submission ran super quick. The difference was around 3 seconds versus 30 seconds. Does joining empty/inactive contests give your problem judging priority? Or is it that the problem set queue is really slow? Let's discuss.

EDIT: Sorry I posted this topic twice. My computer lagged + I double clicked.

You can find the duplicate here: http://codeforces.net/blog/entry/55214

EDIT: Solved. In this problem: 510C - Лиса и имена, I get MLE on test case 12. This is strange as I did not allocate that much space.

My solution: https://pastebin.com/LHY3RiAZ

Data Structures: - 2-D Vector of ints - Stack of ints - Vector of bools to check already visited nodes

Functions: - DFS for topological sort, sorted vertices put in stack - DFS for cycle checking

Is there a memory leak or something? I can't tell.

Thanks, Brad.

EDIT: Solved. It was not a problem with data structures, it was a logical error. I've been doing this greedy problem, and my solution fails on test case 6. For small inputs it seems to work, but for large inputs it produces strange results.

Problem: 854C - Planning

My Solution: https://pastebin.com/MQBNBHEJ

Someone else's accepted solution: 30195313 — They used a priority_queue while I used a sorted vector. This should achieve the same result, and I do not think it is the data structure that is the problem.

Any idea what the problem might be?

UPD: Thanks for all the help guys! I threw away my recursive solution and solved it with loops. (DP?) :>

Hello all,

While going through the USACO training pages problem "Number Triangles", I used a recursive function to calculate the answer. You can see the problem statement here: http://train.usaco.org/usacoprob2?a=nOEpHRAhtUw&S=numtri

I used recursion to try and solve it, but ran into a timeout on test case 6:

> Run 6: Execution error: Your program (`numtri') used more than the allotted runtime of 1 seconds (it ended or was stopped at 1.715 seconds) when presented with test case 6. It used 4312 KB of memory.

I realized that with the test data at hand, it made sense that my program would timeout.

Data:

199 
    1 
    0 1 
    0 1 0 
    0 1 0 1 
    0 1 0 1 0 
    0 1 0 1 0 1 
    0 1 0 1 0 1 0 
    0 1 0 1 0 1 0 1 
    0 1 0 1 0 1 0 1 0 
    0 1 0 1 0 1 0 1 0 1 
    0 1 0 1 0 1 0 1 0 1 0 
    ... [and more] ...

My question is, is it possible for me to optimize my recursive solution, or should I try to use a loop instead of recursion? All hints and advice would be appreciated. (No full solutions please.)

My code below (C++11):