Problem Description
裸的第k短路模板题。给你n个点，m条边，每条边u, v, w代表u - v 的距离是w。给你起点终点，让你求起点到终点的第k短路。
思路：
A* ：设s是起点，t是终点。f(p) = g(p) + h(p); g(p)为当前从s到p所走的路径长度，h(p)为从点p到t的最短路的长度; 这样bfs的时候 因为我们想求最短路，所以每次出来最小的g，如果g相等出来最小的h。h[]可以根据反向建图，求终点到起点的最短路求出。
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define inf 0x3f3f3f3f
struct node
{
int to, w, next;
bool operator < (const node &b) const {
if(w == b.w) return to > b.to;
else return w > b.w;
}
};
node edge[100015];
int head[1015];
node edge1[100015];
int head1[1015], n;
int h[1015], k;
struct node1
{
int to;
int g, f;//g为当前所走的路径长度 f = g + h
bool operator < (const node1 &b) const {//最小堆
if(f == b.f) return g > b.g;
else return f > b.f;
}
};
void dij(int u, int v)//dijkstra + 优先队列（最小堆）
{
memset(h, inf, sizeof(h));//初始化h[]
h[u] = 0;
priority_queue<node> q;
q.push((node){u, h[u]});
while(!q.empty())
{
node t = q.top(); q.pop();
for(int i = head1[t.to]; ~i; i = edge1[i].next)
{
int to = edge1[i].to, w = edge1[i].w;
if(h[to] > h[t.to] + w)
{
h[to] = h[t.to] + w;
q.push((node){to, h[to]});
}
}
}
}
int bfs(int u, int v)
{
int cnt = 0;
if(h[u] == inf) return -1;//无法到达输出-1
if(u == v) k++;//如果回到自身 k++因为一会儿出栈的时候cnt++为了抵消掉
priority_queue<node1> q;
q.push((node1){u, 0, h[u]});
while(!q.empty())
{
node1 t = q.top(); q.pop();
if(t.to == v)//每到达终点一次cnt++;
{
cnt++;
}
if(cnt == k)//如果达到第k次返回 距离
{
return t.g;
}
for(int i = head[t.to]; ~i; i = edge[i].next)
{
int to = edge[i].to, g = edge[i].w + t.g;
int f = g + h[to];//附近的点进入队列
q.push((node1){to, g, f});
}
}
return -1;//找不到第k短路
}
void add(int u, int v, int w, node edg[], int hea[], int &cnt)//前向星存图
{
edg[cnt].to = v;
edg[cnt].w = w;
edg[cnt].next = hea[u];
hea[u] = cnt++;
}
int main()
{
int m, i, u, v, w;
while(~scanf("%d %d", &n, &m))
{
int cnt = 0, cnt1 = 0;
memset(head, -1, sizeof(head));
memset(head1, -1, sizeof(head1));
for(i = 0; i < m; i++)
{
scanf("%d %d %d", &u, &v, &w);
add(u, v, w, edge, head, cnt);
add(v, u, w, edge1, head1, cnt1);//反向建图
}
scanf("%d %d %d", &u, &v, &k);
dij(v, u);//求终点到各个点的最短路
printf("%d\n", bfs(u, v));
}
return 0;
}