Some days ago in Petrozavodsk were started training camp. You can see the shedule and results here

Thanks for translation by RodionGork

Problem statement:
Given an oriented graph with N vertices and M edges we are to find all vertex pairs for which exists a path of infinitesimal weight. 

About 2 months ago I wrote an article in russian version on algorithm for this problem. After some more work and with the help of new idea provided by Narg, I created an improved version of the algorithm. Here is its description 

Step 1. Build condensation of the graph. For each of strongly connected components (SCC) check, whether it contains any loop of negative weight - if so, paint all vertices of this SCC black - otherwise paint them white. 

Now note that if any strongly connected component (SCC) contains a negative-weight loop, then any pair of vertices from this component have infinitesimal-length path between them, since when building a path for any pair we could enter negative-weight loop and reduce total weight to any value. 

Use Ford-Bellman algorithm for each of SCC to find out whether it contains negative-weight loop. 

Step 2. For each of vertices perform BFS from it. If some vertex B could be reached from given starting vertex A via path, containing any black intermediate vertex - then the vertex pair (A, B) is one of those we seek for. Remember it or print out. Working this way we could find out all such pairs. 

Time complexity, by steps, is O((N1 + N2 + ... + Nk)*M) = O(N*M) for condensation and Ford-Bellman and O(N*M) for BFS. Summary does not exceed O(N*M).

Memory: O(n + m).

There is the code

I've tested my algorithm against implementation of Floyd by Edward Davtyan. I performed testing for three kinds of graphs: containing almost full set of edges, containing about quarter of this amount of edges and containing only about 1/20 of full set of edges. 

There is the test generator

Results:

I long ago came a question, what is more important for programmer: standard or nonstandard approach to the problem?

First of all, every problem is a creative, and you must reduce the problem to a simpler. You have several standard methods: to look to restrictions, and through experience you can see obvious standard solution(for example, restrictions is 100000 and you can understand that author thought about sort or segment tree). But in order to understand what condition you can imposed on the problem-you must understand, what restrictions and why you can impose to the problem, you must be creative.

There is some problems which cannot be solved if you haven't nonstandart solution. There is some problems which have more and more easy solution if you think a couple of minutes.

But sometimes your creative may prevent you from solve the problem. For example, if you have the restrictions who are not fully understood: solution with which the asymptotic is correct? And you think about n*logn when there is no correct solution n*logn, and correct solution is n*n. And creative programmers solve problems in implementation more long time.

Of cource, you can't told what is more matter for the programmer-creative or noncreative. I asked you: what tasks you solve simpler-implimentation or creative?