## 11792 - Krochanska is Here!

Moderator: Board moderators

Ronok1307
New poster
Posts: 8
Joined: Tue May 29, 2012 7:37 pm

### 11792 - Krochanska is Here!

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
New poster
Posts: 2
Joined: Thu Oct 23, 2014 9:34 pm

### Re: 11792 - Krochanska is Here!

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 .

This is my first post on this forum

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11792 - Krochanska is Here!

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.
Check input and AC output for thousands of problems on uDebug!

Tawcharowsky
New poster
Posts: 2
Joined: Thu Oct 23, 2014 9:34 pm

### Re: 11792 - Krochanska is Here!

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11792 - Krochanska is Here!

Yes C++ is faster but other people have been able to get AC using Java.
Check input and AC output for thousands of problems on uDebug!