题意 : 求一张有向图S->T的K短路。
思路 : 经典题目。 K短路最简单并且最暴力的方法是从起始点S爆搜下去, 把到达的x的距离d[x]不停的加入到一个优先队列中去, 最后然后每次取出最短距离节点u,然后cnt[u]++一直到到达了u = T && cnt[u] = k结束搜索。 这个方法复杂度似乎是O(M*K),对于这道题目是超时或者爆内存的 = = 。
网上看了下比较好也比较容易写的方法是A*: 评估函数f(x) = g(x) + h(x) ( f(x) 小的优先级高, 先搜),g(x)表示的是从S到x现在搜索到的距离,不断用最短的f(x),更新, h(x)表示从x到T的最短距离(建立反向边用Dijkstra或者spfa算法预处理出来),这样利用A*优化搜索可以AC这道题目。
PS :虽然AC了但是这种方法给我的感觉还是很暴力(但是据说一般都是可以做了的), 汗.... k - 短路问题网上还有一种叫做Yen的算法, 但我不会, 下次补齐。:(