POJ2449 Remmarguts' Date

A*+Dijkstra=Kth-shortest-path

概述

这道题好久之前写的..

因为坚持写博客有好处，而且zrt犇留的作业里也有这道题，所以还是决定了要重温下这道题的解法

https://code.csdn.net/snippets/1631890

裸的第k短路么..

A*加反向图的单源（当估价）解。

第几次从队列里弹出点i，则就找到了点i的第几短路

终止条件

必要性和合理性

题目出题者不会总是很善意地。。。

如果这张图压根没有第k短路（比如本来就不联通，或者通路条数小于k）。。因为A*不终止，会把能求出第NNN短路的所有点都试着求下去…

如果图没环，那不会造成问题。但是要是有个正环（怎么会有负环..），那算法就不会停机了.

思路

更新到目标点的第k短路上的所有点更新次数都不能超过k

人家已经是第k+1短路了，从这个点继续往下搜肯定得到的是大于等于k+1短路的路径，和答案不会有关系，没有必要再扩展它了。

实现

int time[maxn];
//...
if(++time[mn.second]>k) continue;
//....
           

编写中出现的一些秀逗导致的错误

看你能找到错误吗..

#define REP(i, s, e) for(int i=s; i<=e; ++i)
REP(j, , in[mn.second].size()-)
{
    /*...
    ...*/
}
           

就算里面什么也不写，这段代码也足以导致超时了。、

为什么TAT？

因为STL中的容器元素size()返回的是0~npos的非负整数！！

unsigned int 类型只能存储非负整数，因为它根本没有设置符号位和补码

如果容器空，则size()-1不是-1，而是214748347

谨此。