Dima and Bacteria - 400D - Codeforces
Dima and Bacteria - 400D - Codeforces

http://codeforces.com/problemset/problem/400/D

So basically run a BFS to make sure the nodes of same type are
connected. If they are connected, we can compress the graph
because you can travel between any two nodes of the same type
for zero cost. After compressing the graph into a graph with
the number of nodes, run Floyd Warshall on it to get the required
cost matrix

PS: Didn't take me long to come up with the solution, but my
implementation skills are VERY rusty. Another bug because of the
fact that I used a crappy method to do one of the easiest things,
leading to a wrong answer. Also, it took me a lot of time to write
the solution too.

paramsingh/cp,paramsingh/cp,paramsingh/cp,paramsingh/codechef-solutions,paramsingh/codechef-solutions,paramsingh/cp,paramsingh/cp,paramsingh/codechef-solutions,paramsingh/codechef-solutions