## 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

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

### 11097 - Poor My Problem! :-(

i want to solve this pro,but it always gives me tle or wa
someone could give me some hints or test data ?

//sorry for my poor english
coolguy
New poster
Posts: 30
Joined: Tue Oct 17, 2006 5:59 pm
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
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
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
Contact:
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
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
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
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.
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! :-(

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.