tkdsheep-solution-0058

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

题目大意是给n个点（标号从1到n），有n-1条边将这n个点依次相连，并且这些边都是有向的，即第i个点有一条到第i+1个点的边，可以把这些边理解成大路
然后题目还有额外的m条有向边，连接点i和点j,可以把这些边理解成烂泥小路
现在给很多次查询，每次查询给一个起点s和终点t，求s到t的最短路径，并且这条路径只能【经过1次】烂泥小路

题目大意是给n个点（标号从1到n），有n-1条边将这n个点依次相连，并且这些边都是有向的，即第i个点有一条到第i+1个点的边，可以把这些边理解成大路

然后题目还有额外的m条有向边，连接点i和点j,可以把这些边理解成烂泥小路

现在给很多次查询，每次查询给一个起点s和终点t，求s到t的最短路径，并且这条路径只能【经过1次】烂泥小路