Hello everybody,

I'm trying to solve this problem. But I don't have any ideas. Can someone help me, pls ?

Thanks!

**UPD: I solved it :-)**

# | User | Rating |
---|---|---|

1 | Radewoosh | 3759 |

2 | orzdevinwang | 3697 |

3 | jiangly | 3662 |

4 | Benq | 3644 |

5 | -0.5 | 3545 |

6 | ecnerwala | 3505 |

7 | tourist | 3486 |

8 | inaFSTream | 3478 |

9 | maroonrk | 3454 |

10 | Rebelz | 3415 |

# | User | Contrib. |
---|---|---|

1 | adamant | 172 |

2 | awoo | 167 |

3 | SecondThread | 162 |

3 | BledDest | 162 |

5 | maroonrk | 161 |

5 | Um_nik | 161 |

7 | nor | 160 |

8 | -is-this-fft- | 149 |

9 | Geothermal | 146 |

10 | ko_osaga | 142 |

Hello everybody,

I'm trying to solve this problem. But I don't have any ideas. Can someone help me, pls ?

Thanks!

**UPD: I solved it :-)**

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/02/2023 12:35:35 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Wow, congratulations for solve this problem, I've already blogged here about this problem, but my doubts wasn't full cleared, could you explain your ideas to me ?

My Post

Hi, This problem can be solved using Dijkstra. Let's take a look at group of 3 continous vertices (u_1 -> u -> u_2), the tax equals max(Cost[u_1][u], Cost[u][u_2]).

So with any vertices, I have COST is the minimal amount of tax we have to pay, LAST is the tax of the last edge that we enter the town. Suppose I'm at the two [u] I update the result to the town [v] which is connected with [u] by a road (There are 2 cases: Cost[u][v] > LASTs and Cost[u][v] < LAST).

Beause the tax depends on vertices, it's not hard to understand that if d[u] is the minimal amount of tax to go to the town [u] and we haven't determined d[v], certainly, d[v] = d[u] + tax[v]. So after update [u][v], we can remove the road that connects [u] and [v].

My English isn't good, so I hope you can understand it :-)

My implementation http://ideone.com/eKdUIT