web analytics

地铁 最短路变式题

题目链接:https://ac.nowcoder.com/acm/contest/1112/F

题目大意:中文题,没什么大意.

但是我们发现边上的信息很重要,我们在最短路的时候就要改变一下方式 \(D[i]\)就表示的不再是1 到 i号点的最短路,而表示的是到第i条边的最短路,因为这样我们每次dij的时候压边,我们在松弛的时候就可以获得两条边的信息,这样就可以计算了。