1. 题目

传送门= ̄ω ̄=

2. 题解

依然是最短路条数统计问题。
可以参见这两篇题解:
http://k-xzy.cf/?p=1232
http://k-xzy.cf/?p=1227

只不过这题有坑:
数据中存在重边,需要自行过滤掉。而且重边的权值可能不同,需要保存最小权值。

考虑到数据范围比较小,在1000级别,所以开个二位数组存两点间距离。

而且此题不同于上面两题,是有向图(上面两题都是无向图)。所以建立反向图,权值不变,交换边的起点终点,便于记忆化搜索。

代码: