NIKKEI Programming Contest 2019-2 Task D. Shortest Path on a Line
Observations
①
从 $1$ 到 $N$ 的最短路一定是不走回头路的。所谓走回头路是指从序号大的点走到序号小的点。
证明:首先,任意从 $1$ 到 $N$ 的路径的最后一步一定不是回头路。假设存在一条从 $1$ 到 $N$ 的最短路走了回头路,并设这条路最后一次回头是从 $u$ 到 $v$ 且从 $v$ 开始直到终点经过的点依次是 $v = v_0, v_1, \dots v_k = N$。我们有 $v < u < N$,$v = v_0 < v_1 < v_2 <\dots < v_k = N$ 且 $v_i \ne u$。设 $v_i < u$ 而 $v_{i+1} > u$ 则必然存在边 $(u, v_{i+1})$ 和边 $(v_i, v_{i+1})$ 长度相等,因此走 $u, v_{i+1}, \dots, v_{k}$ 更优。矛盾!
为了便于描述,以下用 $(u, v, C)$ 表示连接 $u, v$,长为 $C$ 的无向边,用 $(u \to v, C)$ 表示从 $u$ 到 $v$ 长为 $c$ 的有向边。
从上述证明可以得出推论:将原无向图按下述方式改造成有向图,从 $1$ 到 $N$ 的最短路长度不变:
以下设 $1 \le u < v \le N$。将原图中的无向边 $(u, v, C)$ 删除,加入有向边 $(u \to v, C)$。
再任意加入长度非负的回头边。
考虑上述有向图的一种特殊情形:对于 $i = i, 2, \dots, N$,加上长度为 $0$ 的回头边 $(i \to i - 1, 0)$。
注意到此时对于一组有向边 $(s \to t, C_i)$,$L_i \le s < t \le R_i$,只保留 $(L_i \to R_i, C_i)$ 仍能保持从 $1$ 到 $N$ 的最短路长度不变。
最新文章
- <;HTML5和CSS3响应式WEB设计指南>;译者序
- 由Vue引发的getter和setter思考
- JVM(java 虚拟机)内存设置
- LA 4329(树状数组)
- cocos2d疑问
- 武汉科技大学ACM:1005: 单位转换
- BAD packet signature 18245 错误解决
- Java PreparedStatement
- Memcached&#183;Redis缓存的基本操作
- [cogs2701]动态树
- C语言程序设计实验第四次作业
- Servlet生命周期与工作原理(转载)
- 如何设制 select 不可编辑 只读
- go 【第二篇】包、变量、函数
- UOJ 【UR #5】怎样跑得更快
- Hibernate properties文件
- Android 集成高德地图
- 747. Largest Number At Least Twice of Others
- LINUX基础实验报告
- yum与apt命令比较,yum安装出现No package vim available解决办法