I have been trying this question for 2 days. I have come up with a solution which binary searches the minimum temperature and for each possible temperature I check the minimum distance by Dijkstra's Algo. It has passed the sample test case as well as all the test cases of uDebug, but it is giving WA in UVA. Can someone give me some test cases where my code may fail. My solution

Thanks.

UPD — I finally got it accepted. UVA judge penalizes for spaces at the end of each line .... feels sad when an entire day is spent "debugging" an AC solution. The above link now contains my AC solution :).