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
11792 - Krochanska is Here!
Moderator: Board moderators
-
- 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 .
I would appreciate your help.
This is my first post on this forum
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
-
- 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.
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!
-
- 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.
WIth your help I solved this problem using c++11 in 149ms but java just isn't fast enough.
-
- 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!