11097 - Poor My Problem! :-(

All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
retptr
New poster
Posts: 1
Joined: Thu Oct 19, 2006 11:53 am

11097 - Poor My Problem! :-(

Post by retptr »

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 :D
coolguy
New poster
Posts: 30
Joined: Tue Oct 17, 2006 5:59 pm

Post by coolguy »

i guess this problem is about modified shortest path problem . can any one tell how to modify the shortest path algorithm so that it meets the necessity of the problem . more over a little explanation may be handy ....
bye bye
In good company
ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon »

can anyone give me the output for the following input?

4 4 0
0 1 100
1 2 1
2 3 1
3 1 1
4
0
1
2
3
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program
Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer »

Hi,

My code gives:

Code: Select all

0.0000 0
1.0990 1000
1.0992 998
1.0991 999

7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
DP
Learning poster
Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Location: Bangladesh
Contact:

Post by DP »

Hi Observer,
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
Is my approache right?
ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon »

no its wrong. consider the test case
3 3 0
0 1 4
0 2 3
2 1 3
1
1

answer should be 3, but your algo will give 4 as it delete the 6 cost age.
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program
rammestain
New poster
Posts: 18
Joined: Fri Apr 21, 2006 11:34 am

Post by rammestain »

I've tried too solve this problem with bell-man ford but I got getting TLE.
I repeat outer loop of bell-man ford while I have a update in inner loop.
Is this true?
Hackson
New poster
Posts: 35
Joined: Sun Nov 10, 2002 5:36 am

Post by Hackson »

rammestain wrote:I've tried too solve this problem with bell-man ford but I got getting TLE.
I repeat outer loop of bell-man ford while I have a update in inner loop.
Is this true?
I solved that by DP.
Note that implementation of the graph really matters, I used adjacency list in this case. :wink:
Solving problem is a no easy task...
liauys
New poster
Posts: 7
Joined: Thu Jul 02, 2009 6:37 pm

Re: 11097 - Poor My Problem! :-(

Post by liauys »

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.
Post Reply

Return to “Volume 110 (11000-11099)”