1377：最优乘车(travel)_1377 最优乘车

题目描述

题目出处：点这里

输入

输出

样例

输入：

3 7
6 7
4 7 3 6
2 1 3 5

输出

2

分析与思路

先以各个站点为顶点，以各线路为边，画出图来，这个图长这样

唔，好像有一点复杂，而且如何求出旅客朋友的换乘次数（切换线路的次数）呢？这又使我们犯了难

换个想法

如果能把求换乘次数转换成求最短路径，如果两顶点涉及换乘，边权就为一，在使用Dijkstra算法求出最短路径的长，我们就可以解决这个问题了，那么如何转化呢？

添边

今天的主角终于闪亮登场------添边
那么什么是添边呢，如何添边，添出来的边的边权是什么，添边的目的是什么？

定义

添边，顾名思义，是在图内的两端点之间增加一条边，使两端点相连

如何添边

添边是有条件的，那么，在这个题目当中，我们应如何添边呢？
举个栗子：由于本题目所求的是换乘次数而不是最短路径，所以，只要起点与另外一端点之间本没有边联系时，我们就可以在两端点之间添边

如何给添出来的边赋值边权

按照上面的方式，我们得到了这样的图

这个人手怎么这么抖，线都画不直
那么，新添出来的边的边值要如何确定呢？
分两种情况：
一，起点原本就可以到达该顶点
和我们最开始想的一样，若两顶点涉及到换乘的话，边权为一
二，起点原来无法到达该顶点
如果本就无法到达，那么为了不使这一条边影响Dijkstra算法的计算，我们要把边权赋值为无穷大，这样，当Dijkstra算法计算时，就会自动排除这一条边

添边的目的

看到上面的图，可能有的人眼都直了（没错就是我 ），这难道不是把图变复杂了吗，这对我解出这道题有什么帮助吗？
图确实复杂了，但题目却因此简单起来了
对于这道题，在添边前，我们的想法大概是这样的

这个人箭头画的好丑啊
然而，当我们换一种思路，使用添边，并把问题转换成最短路径问题时，我们的想法就比上面简单了10^18倍，大概想法如下

箭头画的真的好丑
看，题目和思路变得简单了起来，接下来就可以利用这个思路解决这个问题了

最后的最后

从今天这个题上也能看出来，有时候思路是要转化的，不能死钻一个牛角尖~