小A 最近学习了最短路算法,例如Bellman–Ford,Dijkstra等,他们可以在一定的时间内求解由起点 到其他所有点的最短路的长度。“但是对于边数很大的图,就不能直接用最短路算法求解,我们可以考虑这个图是否有什么特殊的性质....”老师小 T 在课上说道。
课后,小 A 的老师小 T 给小 A 留了一个问题:给定 个点的图,第 个点到第 个点有一条单向边,边权是 。除此之外,还有 条额外的双向边,第 条边连接了第 和第 个点,边权为 。请求出第 个点到第 个点的最短路长度。
由于小 A 上课打摆去了,所以自然是不会做的,所以他请你帮帮他。