HBC20183[JSOI2010]旅行题解

想要检验自己的编程水平？来试试全网最全C++题库，让您在挑战中不断进步。

WJJ喜欢旅游，这次她打算去一个据说有很多漂亮瀑布的山谷玩， WJJ事先得到了一张地图，上面标注了N(1 ≤ N ≤ 50)个小动物的聚居地，也就是一个个的小村落，其中第1个村 庄是WJJ现在住的地方，第N个村庄是WJJ打算去的地方， 这些村庄之间有M(1 ≤ M ≤ 150)条双向道路连接着，第j 条双向道路恰好直接连接两个小村庄A，B，长度为

WJJ喜欢旅游，这次她打算去一个据说有很多漂亮瀑布的山谷玩。 WJJ事先得到了一张地图，上面标注了N(1 ≤ N ≤ 50)个小动物的聚居地，也就是一个个的小村落。其中第1个村 庄是WJJ现在住的地方，第N个村庄是WJJ打算去的地方。 这些村庄之间有M(1 ≤ M ≤ 150)条双向道路连接着，第j 条双向道路恰好直接连接两个小村庄A，B，长度为C(1 ≤ A，B ≤ N，Ai < > B, 1 ≤ C ≤ 1000)。道路有的是隧道，有的是栈桥，地图上那些看起来在村庄之外交叉的路实际上并不相交——也就是说，如果把这些小村落和双向道路构成的道路网看作图论意义上的图，我们不保证它是平面图，也不保证它没有重边。 不过，有一点还是可以保 证的：WJJ细心地验证过，从它居住的村落一定能走到她想去的那个山谷。 在WJJ所在的神奇世界中，每只小动物都可以借助仙人掌来施放魔法，其中之一是，交换世界中任意两条双向道路 的长度，同时保持其他道路的长度不变。 按WJJ目前的魔法水平，她最多能使用K(1 ≤ K ≤ 20)次这种道路长度交换魔法。可惜的是，由于仙人掌刺比较多，WJJ并不打算带着它旅行，于是她会在家里完成想要的道路交换后再出门。假设WJI的旅行途中不会有其他小动物进行道路交换来破坏她设计好的路线。 为了尽快达到目的地，WJJ希望她需要走的总距离越短越好。也就是说，使用最多K次魔法后，从村落1到村落N的最短距离是多少？

不断学习，不断挑战，才能在编程领域中脱颖而出！全网最全C++题库，助您成为编程高手！

标签： HBC20183[JSOI2010]旅行题解