i want to solve this pro,but it always gives me tle or wa
someone could give me some hints or test data ?
thx advance;
//sorry for my poor english
11097  Poor My Problem! :(
Moderator: Board moderators
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Hi Observer,
What is the algorithm of you? Is it the following way:
Is my approache right?
What is the algorithm of you? Is it the following way:
Code: Select all
1. First run Dijkstra for minimum cost
2. then delete all cost of greater than this minimum cost.
3. then run bfs for minimum edge

 New poster
 Posts: 18
 Joined: Fri Apr 21, 2006 11:34 am
I solved that by DP.rammestain wrote:I've tried too solve this problem with bellman ford but I got getting TLE.
I repeat outer loop of bellman ford while I have a update in inner loop.
Is this true?
Note that implementation of the graph really matters, I used adjacency list in this case.
Solving problem is a no easy task...
Re: 11097  Poor My Problem! :(
Hello everyone, I'm solving this problem with dp.
Let best[k][v] be the minimum path cost to reach vertex v, passing through k number of edges along the path.
Am I on the right track? I got the same output for the datasets given in the discussion above. Are they any tricky cases? And I added an EPS to the final result to avoid rounding errors. Really hope someone to enlighten me! Thanks you.
Let best[k][v] be the minimum path cost to reach vertex v, passing through k number of edges along the path.
Am I on the right track? I got the same output for the datasets given in the discussion above. Are they any tricky cases? And I added an EPS to the final result to avoid rounding errors. Really hope someone to enlighten me! Thanks you.