OJ Board

I have interesting problem.

given weighted indirected graph.
number of vertex n(n <= 30000)
number of edges m(m <= 50000) and a,b,c.

you have tu find shortest path between a and b vertexes and this shortest path should contain vertex c. you can't path one vertex twice.

I can't solve this problem. can anybody help me to solve it?

There's a very recent thread about this problem:
http://online-judge.uva.es/board/viewtopic.php?t=21028

If you don't understand my explanation in that thread, feel free to post any questions you have there.

thanks
but I have to study min-cost max-flow algorithm at first. my friend told me that this algo is very hard to code

It's not much harder than usual maximum flow problem. Basically, if you use Ford-Fulkerson algorithm for maximum flow, and always use cheapest augmenting paths, then you'll get a maximum flow of minimum cost. That's almost all about it :)

While finding cheapest paths, you should assume that cost of reverse edges in the flow network is negative of the cost of direct edges (i.e. you get your money back when you decrease flow along original edges).
Because of this thing, some edges will have negative cost, and so you can't use plain Dijkstra algorithm to find shortest paths. But fortunately there's a special transformation you can use for edges' cost which allows you to use Dijkstra: let phi[x]=0 initially for all vertices x. At each Ford-Fulkerson's iteration find shortest path from source to sink with edge weights w'(u,v) = w(u, v) + phi - phi[v], and then increase each phi[x] by the distance from the source to x. This transformation changes cost of all source-sink paths by only a constant, and keeps modified edge weights positive, so that you could use Dijkstra's algorithm.

Here are a few links to actual implementations:
- http://shygypsy.com/tools/mcmf4.cpp
- http://ilyaraz.fatal.ru/src/brides.html
- some of the submissions to TCCC07 round 2's JobPlanner problem.