测试地址：Remmarguts' Date
题目大意：给出一个有N个点，M条边的有向图，求从S到T的大于0的第k短路的长度。
做法：这是一个图上的搜索问题，可以用A*算法解决。估价函数f(n)=g(n)+h(n)，其中g(n)为从起点到节点n的路径长度（可以不是最短，因为有可能走过重复边），h(n)为从节点n到终点的最短路径长度（真实值）。这样的话，当节点T第k次被访问时，此时的g(k)就是答案。
懂得主要做法之后，还有一些小问题需要解决：
如何求出每个节点的h值？答：用dijkstra或者SPFA跑一遍反图，求出源点为T的单源最短路即可。
在什么情况下继续拓展就不可能有解了？答：当访问一个节点超过k次的时候，就不用继续拓展了，因为继续下去肯定不能找到第k短的路径了。
眼尖的同学肯定已经发现了，我在描述题目大意的时候，“大于0的”这几个字加粗了，为什么要强调这个条件呢？因为题目中存在S和T相等的情况，因而最短的路径就是0，然而题目中所要求的路径必须要存在边，所以这不算一条路径。那么怎么处理呢？将k赋值为k+1即可。
以下是本人代码：
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#define inf 1000000000
using namespace std;
int n,m,first[1010]={0},qfirst[1010]={0},tot=0,S,T,k;
int h[1010];
bool vis[1010];
struct {int v,c,next;} e[100010],qe[100010];
struct state
{
int v,g,h;
bool operator < (state a) const
{
return a.g+a.h<g+h;
} //使用STL的优先队列，需要重载运算符
};
void insert(int a,int b,int c)
{
e[++tot].v=b;e[tot].c=c;e[tot].next=first[a];first[a]=tot;
qe[tot].v=a;qe[tot].c=c;qe[tot].next=qfirst[b];qfirst[b]=tot;
}
void spfa() //SPFA跑反图，用dijkstra也可以
{
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++) h[i]=inf;
queue<int> Q;
Q.push(T);h[T]=0;
while(!Q.empty())
{
int v=Q.front();
Q.pop();
for(int i=qfirst[v];i;i=qe[i].next)
{
int j=qe[i].v;
if (h[v]+qe[i].c<h[j])
{
h[j]=h[v]+qe[i].c;
if (!vis[j]) {Q.push(j);vis[j]=1;}
}
}
vis[v]=0;
}
}
int AStar() //A*
{
priority_queue<state> fq;
state now,next;
now.v=S,now.g=0,now.h=h[S];
fq.push(now);
int cnt[1010]={0};
while(!fq.empty())
{
now=fq.top();
fq.pop();
cnt[now.v]++;
if (cnt[now.v]>k) continue;
if (cnt[T]==k) return now.g;
for(int i=first[now.v];i;i=e[i].next)
{
next.v=e[i].v;
next.g=now.g+e[i].c;
next.h=h[e[i].v];
fq.push(next);
}
}
return -1;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int s,t,c;
scanf("%d%d%d",&s,&t,&c);
insert(s,t,c);
}
scanf("%d%d%d",&S,&T,&k);
if (S==T) k++; //特殊情况，S=T
spfa();
printf("%d",AStar());
return 0;
}