`Algorithm-Solution` `AcWing` 903. 昂贵的聘礼

link

Solution

Firstly, we can transform this question to a graph, let all points $0,n-1$ and a virtual point $n$

• the original price of $i$ is $a$, then it corresponds to a directed edge $i\to n$ with weight $a$.
• the new price of $i$ is $a$ if you possess $j$, then there is a directed edge $i\to j$ with weight $a$.

We got a directed positive-weighted graph.

If we don’t consider the Rank-Constrain, the answer is the minimal path from $0\to n$.

The answer path non contains any loop, but the graph will contains loop.

---

If you use DFS + Remembered-DP, that is erroneous, because this graph is not a DAG.

e.g.

0------->1---->2
|        ^     |
|        |     |
|        |     |
-------->3<-----
1
2
3
4
5

DFS(0), if it visit 1 firstly, then go to 2, and when we arrive at 3, it will also DFS(1), but DFS(1) is not finished, so $Distance[1]$ is wrong, then $Distance[3]$ is also wrong.
Consequently, when $0\to 3$, $3$ returns a wrong Distance.
(suppose the answer is $0\to 3\to 1\to 2\to n$)

---

The right approach is just Dijkstra.

---

Let’s consider Rank-Limitation, it’s vital to comprehend the meaning.
Although you just have one stuff $0$, but you may involve many staffs in the whole process.
More precisely, for a path $0\to 1\to 2\to n$, you involved $0,1,2$.
The Rank-Limitation shows that the rank $a,b$ of any two staffs in the path, should satisfying $|a-b|\le M$
So, we scan all the possible interval $[1,1+M],[2,2+M],[3,3+M],...$ denotes that a point is valid in the graph if the rank of the point locates in the interval.
There are some crucial points:

• don’t consider the rank of virtual point $n$, i.e., $n$ is always valid. You should handle it specially.
• For a interval $[l,r]$ (the rank of all points within the interval), the start-point $0$ should also satisfies this interval. Although if it outsides the interval means that this interval has no solution, that is what it is according to the definition! (if you ignore the rank of $0$, it will be erroneous; e.g., $0\to 1\to 2\to n$ (the rank are $4,1,2,?$) for the limit interval $[1,2]$, this path is invalid)