Hi guys,

I was looking for min-cost-max-flow problems and found this

http://www.spoj.com/problems/GREED/

I coded solution, submitted it and received AC with about 20s time. Unfortunately, there are accepted runs with time less than 2s.

I guess my solution in so slow because of my poor implementation of the algorithm.

Can somebody take a look on my solution and tell me what I'm doing wrong?

my solution

UPD: I've implemented Dijkstra's algo with potentials, and ... accepted this problem with 40s. Twice slower! I don't know, what's wrong with me? :/

My new solution with Dijkstra

UPD2: Changed algorithm to use Dijkstra for sparse graph. However, received AC with ~40s. OMG, WHAT IS WRONG WITH MY CODE?

Algo using Dijkstra for sparse graphs

Thanks in advance.

Attention Hackers! The dates have been set for Facebook Hacker Cup 2013.

Jan 7 — Jan 27 — Registration

Jan 25 — Jan 27 — Online Qualification Round

Feb 2 — Online Elimination Round 1

Feb 9 — Online Elimination Round 2

Feb 16 — Online Elimination Round 3

March 22 -23 — Onsite Finals at Facebook

For more details visit official page.

UPD : Registration is now open for the 2013 Facebook Hacker Cup! If you registered for a previous year, you're automatically registered for this year, but you should check to make sure all of your information is up-to-date. The qualification round begins on January 25th. Good luck!

https://www.facebook.com/hackercup/register

Please, somebody, explain me, how to solve 10E?