题目描述
k短路模板题
spfa + A*
建议先去其他的大佬那看懂A*,如果还不懂可以看看我代码里的注释
C++ 代码
//* k短路
//* http://poj.org/problem?id=2449
//* A*搜索核心:f[i] = dis[i] + dist[i];
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1010;
const int M = 100010;
struct edges
{
int v, len, next;
}edge[M], reEdge[M];
int h[M], idx; //正向tu
int reh[M], reidx; //反向图
int n, m; //点数和边数
int s, t, k; //s到t的第k短路
int dis[M]; //存反向图的最短距离
bool st[M]; //spfa中判读一个点在不在队列里
int cnt[M]; //在Astar中记录一个点被访问了多少次
struct astar //A*搜索时的优先队列
{
int v, dist;
bool operator< (const astar &a)const
{
return dis[v] + dist > dis[a.v] + a.dist;
}
};
// todo 初始化
void init()
{
memset(h, -1, sizeof h);
memset(reh, -1, sizeof h);
}
// todo 建图,同时建正向的和反向的
void add(int u, int v, int len)
{
edge[idx].v = v;
edge[idx].len = len;
edge[idx].next = h[u];
h[u] = idx++;
reEdge[reidx].v = u;
reEdge[reidx].len = len;
reEdge[reidx].next = reh[v];
reh[v] = reidx++;
}
// todo spfa求t到其他点的最短路
void spfa()
{
memset(dis, INF, sizeof dis);
dis[t] = 0;
st[t] = true;
queue<int> q;
q.push(t);
while(q.size())
{
int x = q.front();
q.pop();
st[x] = false;
for(int i = reh[x]; i != -1; i = reEdge[i].next)
{
int j = reEdge[i].v;
if(dis[j] > dis[x] + reEdge[i].len)
{
dis[j] = dis[x] + reEdge[i].len;
if(!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
}
// todo 用A*算法求第k短路
int Astar()
{
if(dis[s] == INF)
return -1;
astar S; //从s点出发
S.dist = 0; //s到自己的距离为0
S.v = s;
priority_queue<astar> q;
q.push(S); //把s加入pq,开始搜索
while(q.size())
{
astar tmp = q.top(); //取出f[i]最小的一个
q.pop();
cnt[tmp.v]++; //记录一下被取出的次数
if(cnt[t] == k) //如果t这个点已经被访问过k次了
return tmp.dist; //就返回答案
if(cnt[tmp.v] > k) //如果一个点被取出超过了k次就不用再考虑了
continue;
for(int i = h[tmp.v]; i != -1; i = edge[i].next) //从正向搜点,然后逐个更新期望f[i]
{
astar near;
near.dist = tmp.dist + edge[i].len;
near.v = edge[i].v;
q.push(near);
}
}
return -1;
}
int main()
{
init();
cin >> n >> m;
for(int i = 1; i <= m; i++)
{
int a, b, t;
scanf("%d%d%d", &a, &b, &t);
add(a, b, t);
}
cin >> s >> t >> k;
spfa();
if(s == t)
k++;
int tmp = Astar();
cout << tmp << endl;
return 0;
}