Roads in Berland

Source: Codeforces 25C

1. Read the problem and summarise the task requirements.
   • Try to keep your response to a couple of sentences.

We are interested in the sum of all pairs shortest paths.

2. How many new roads will be built, and how much time (asymptotically) can we spend assessing the impact of each of them?

3. For a given pair of cities, can a new road (anywhere in Berland):
   • increase the distance between them,
   • keep the distance between them unchanged, or
   • decrease the distance between them?
4. For the outcomes above that are possible, characterise the circumstances in which each of them occurs.
   • Remember that roads go both ways!
5. Can you test each pair of cities as fast as you found to be necessary in Question 2?
   • You’ll need to not just identify whether there is a change, but also quantify how much change there is.

6. Design an algorithm to solve the problem.

7. Analyse the time complexity of your algorithm and estimate its running time.

8. Implement this algorithm in code.
   • Reflector:
     • What potential pitfalls can you think of?
     • Write some tests to check for these pitfalls.
   • Other group members:
     • Write a program which solves the problem.
   • Run your tests and debug if necessary.
9. Submit your program for judging!
   • Debug as required.