11792 - Krochanska is Here!

[Ronok1307]

Could someone clarify the problem statement for me? From what I understand it is either

a) Find an important station form which the cost of visiting all other stations is minimum --(if multiple answers)--> Find the important station from which the cost of visiting all other important stations is minimum --(if multiple answers)--> Find the important station with the minimum ID number

OR

b) Find the important station from which the cost of visiting all other important stations is minimum --(if multiple answers)--> Find the important station with the minimum ID number

EDIT : Ok, I figured it out. It's B

[Tawcharowsky]

Hi there,

does anyone know more efficient algorithm for solving this other than running bfs numOfImportantStations times.
While that may work in c/c++, it produces TLE in java .
I would appreciate your help.

This is my first post on this forum

[brianfry713]

It is possible to solve this problem using Java.
Try creating a graph with only the important stations and then run the Floyd-Warshall algorithm.

[Tawcharowsky]

Thank you brianfry713, for you reply.
WIth your help I solved this problem using c++11 in 149ms but java just isn't fast enough.

[brianfry713]

Yes C++ is faster but other people have been able to get AC using Java.