Привет, кодфорсес!
Недавно наткнулся на вот такую интересную задачу (и к сожалению не смог придумать оптимальное решение): Дается неориентированный граф из N <= 10^5 вершин и M <= 2*10^5 ребер. Каждое ребро имеет цвет c_i <= 10^6. Необходимо найти минимальную цену пути от вершины 1 до вершины N, причем цена пути рассчитывается следующим образом: поочередно выписываются цвета ребер в пути, а далее считается количество подотрезков с одинаковыми цветами. Пример: N=4, M=4, ребра: 1<->2 с цветом 1, 2<->3 с цветом 2, 3<->4 с цветом 1, ребро 1<->3 с цветом 1.
Если мы пойдем путем 1->2->3->4, то итоговая цена будет 2, т.к. мы выпишем цвета ребер: 1,2,1,1, и тут будет 3 подотрезка где цвета одинаковы: [1; 1], [2; 2], [3; 4]. Но если мы пойдем путем 1->3->4, то цена будет 1, т.к. у всех ребер на пути цвет 1.
Прошу помощи в решении данной задачи и заранее благодарю!
This is a constructive graph problem.
In this problem, we want to walk through the path switching colors as few times as possible.
So we set the value of all edges to $$$0$$$. create a staging point of value $$$0$$$ for edges of the same color, and a staging point of value $$$1$$$ for edges of a different color.
Then the shortest path $$$-1$$$ is the answer.
For the example in blog, your solution will give answer 3, won't it?
Sorry, I didn't take into account the incoming edge at the start and end, the answer should have been -1, I've amended it.
It seems that there are still many holes in my thinking and I thank the blogger for asking such a good question. The corrected formula should be x/2. (Why my reply looks so much like chatGPD)
That's ok! However, I think this is still a little bit incorrect. Actually, the value shortest_path should be divided by two. This is because we are entering and leaving every group of colors exactly two times, therefore we calculate it two times in our answer. Thanks a lot for such a cool idea!
Can you provide the link for this problem please?
I came up with statement on my own. I tried to search it on the web, but didn't find any similar problem.
It's probably ARC061E I think. The constraints for $$$n$$$, $$$m$$$ and $$$c_i$$$ is the same too.
Cool, this is actually the same problem I wanted to solve!