2017景驰无人驾驶 1024编程邀请赛 A题

未分类

---

题意：
众所周知，蒜蒜是一名热爱工作的好员工，他觉得时间就是金钱，做事情总是争分夺秒。
这天晚上，蒜蒜一个人去吃晚饭。不巧的是，吃完饭以后就开始下雨了，蒜蒜并没有带雨伞出来。但是蒜蒜热爱工作，工作使他快乐，他要尽快赶回去写代码。
蒜蒜的公司在中关村，中关村这边地形复杂，有很多天桥、地下通道和马路交错在一起。其中，地下通道是可以避雨的，天桥和马路都没办法避。可以把中关村抽象成为一个有$n$个点的地图（顶点编号为$1$到$n$），其中有$m_1$条地下通道，有$m_2$条马路或者天桥，其中地下通道的长度为$1$。蒜蒜吃饭的地方在点$1$，公司在点$n$。当然，蒜蒜虽然爱工作心切，但是他更不想淋很多雨，同时也不想浪费很多时间。于是他想了一个折中的办法－－在保证他回到公司所走的路程总和小于等于$L$的情况下，他希望淋雨的路程和尽量的少。
求在总路程小于等于$L$的情况下，最小的淋雨路程。

数据范围:
$2\leq n \leq 100,0\leq m_1 \leq 50,0\leq m_2\leq 5000,1\leq L\leq10^8$.

题解：
由于$m_1$比较小，所以可以从$m_1$的角度下手，定义$dis(i,j)$$(0\leq i \leq m_1,1\leq j \leq n)$表示经过恰好$i$条地下通道，到达$j$点的最短路.显然$dis(0,1)=0$，其他的初始化为$INF$.

跑最短路时如果边是地下通道：

$$\begin{align*} dis(i+1,v)=min(dis(i+1,v),dis(i,u)+cost(u,v)) \end{align*}$$
否则:
$$\begin{align*} dis(i,v)=min(dis(i,v),dis(i,u)+cost(u,v)) \end{align*}$$
相当于跑$n*m_1$个点，$m_1*m_2$条边的最短路.
$$\begin{align*} ans=min\{dis(i,n)-i|dis(i,n)\leq L\} \end{align*}$$
注意判无解.