I found an interesting problem in the archive of Iran National OI problems. The problem statement in English is:
Let D be a weighted directed graph. The length of a path P is defined as the minimum weight of the edges along P. The distance between vertices u and v is the maximum length among all paths from u to v. Your task is to find the distance between every pair of vertices in O(n·e + n²) time.
I have a O(n(e + n) lg n) solution for this using Dijkstra, but I haven't been able to solve it in O(n·e + n²), so I'm looking for a solution. Any help would be appreciated!
