A*的概念主意在于估计函数，f(n)=g(n)+h(n)，f(n)是估计函数，g(n)是n节点的当前代价，h(n)是n节点的估计代价；而实际中，存在最优的估计函数f'(n)=g'(n)+h'(n)，那么显然我们在A*的估计中，h(n)<=h'(n)，否则你将搜不到最优解；（g(n)>=g'(n)我还不怎么清楚为什么啊，大多数情况是g(n)=g'(n)，这个可以不用管吧。。）
求s->t的第k短路，
dist[x]为x->t的最短路 （这个只要反向建边，然后一次spfa，求出任意点到t点的距离即可
那么点x的g(x)=到达当前点的花费
h(x) = dist[x] , 可以知道h(x)=h'(x)，所以可以保证搜到最优解。
每次出出队列的都是当前f(x)最小的点，
所以如果点x出队列， 那么就cnt[x]++,
当cnt[x]==k时，那么当前的f(x)就是第k短路，因为第一次出队列时，肯定是最短路上的点，第二次是次短路上的点，第k次，自然就是第k短路上的点了。
#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <stdio.h>
#include <string.h>
#include <time.h>
#include <math.h>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <bitset>
#include <algorithm>
#include <iostream>
#include <string>
#include <functional>
#include <iostream>
typedef __int64 LL;
const int INF = << ; /*
*/
const int N = + ;
struct Node
{
int from, to, dis, next;
}g[N*];
int head[N], e;
int dist[N];
bool vis[N];
int cnt[N];
void addEdge(int u, int v, int dis)
{
g[e].from = u;
g[e].to = v;
g[e].dis = dis;
g[e].next = head[u];
head[u] = e++;
} void spfa(int src, int n)
{
for (int i = ;i <= n;++i)
dist[i] = INF;
std::queue<int> q;
q.push(src);
dist[src] = ;
while (!q.empty())
{
int u = q.front(); q.pop();
vis[u] = false;
for (int i = head[u];i + ;i = g[i].next)
{
int v = g[i].to;
if (dist[v] > dist[u] + g[i].dis)
{
dist[v] = dist[u] + g[i].dis;
if (!vis[v])
{
vis[v] = true;
q.push(v);
}
}
}
}
}
void init()
{
e = ;
memset(head, -, sizeof(head));
}
void reverse()
{
memset(head, -, sizeof(head));
int te = e;
e = ;
for (int i = ;i < te;++i)
addEdge(g[i].to, g[i].from, g[i].dis);
}
struct Node2
{
int to;
int g;
bool operator<(const Node2&rhs)const
{
return g + dist[to] > rhs.g + dist[rhs.to];
}
};
/*
因为每次出队列的都是最短的， 所以该点是第几次出队列，就表示是该点到终点的第k短路
*/
int aStar(int src, int des, int k)
{
std::priority_queue<Node2> q;
Node2 cur, tmp;
cur.to = src;
cur.g = ;
q.push(cur);
while (!q.empty())
{
cur = q.top(); q.pop();
int u = cur.to;
cnt[u]++;
if (cnt[u] > k) continue;
if (cnt[u] == k)
return cur.g + dist[u];
for (int i = head[u];i + ;i = g[i].next)
{
int v = g[i].to;
tmp.to = v;
tmp.g = cur.g + g[i].dis;
q.push(tmp);
}
}
return -;
}
int main()
{
int n, m, src, des, k;
while (scanf("%d%d", &n, &m) != EOF)
{
init();
int u, v, dis;
for (int i = ;i <= m;++i)
{
scanf("%d%d%d", &u, &v, &dis);
addEdge(v, u, dis);
}
scanf("%d%d%d", &src, &des, &k);
spfa(des, n);
reverse();
if (src == des)k++;//如果起点等于终点，那么最短路其实是什么都不走
int ans = aStar(src, des, k);
printf("%d\n", ans);
}
return ;
}