11097 - Poor My Problem! :-(

[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

[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

[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

[Observer]

Hi,

My code gives:

Code: Select all

0.0000 0
1.0990 1000
1.0992 998
1.0991 999

[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]

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.

[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]

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.

[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.