uva 11284:
All pairs shortest path (Floyd) + dynamic programming