双倍经验

思路

如果使用正常的dijkstra算法，我们并不知道访问到终点的时候是不是最小的路径，所以需要不断进行最小值的取值。此时我们可以使用A*算法。

什么是A*？A*是一种BFS的优化方式，其核心就是估价函数。什么是估价函数？估价函数就是评估当前状态距离目标状态所粗略估计的距离，要求小于等于真实的距离，通常以较低的复杂度解决。A*所具有的独特的排序方式就是按照$当前距离+估计距离$进行排序。

以本题举例，当前状态就是从开始节点到当前节点的距离，估价函数就是当前节点到终点的距离（此时就是等于真实距离），先以终点为起点跑一遍dijkstra，再以起点为起点跑一边A*，就可以保证每次访问到一个节点一定是按照最短的路径走的了，每次访问到终点输出当前长度即可。

B27 A*算法 第K短路

#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

const int N = 1010, M = 200010;
int h[N], rh[N], to[M], w[M], ne[M], tot;
void add(int h[], int a, int b, int c)
{
	to[++tot] = b;
	w[tot] = c;
	ne[tot] = h[a], h[a] = tot;
}
int n, m, S, T, K;
int f[N], vis[N], cnt[N];
struct node
{
	int s, v, d; // s排序，v点，d距离
	bool operator<(const node &x) const
	{
		return s > x.s;
	}
};

void dijkstra()
{
	memset(f, 0x3f, sizeof f);
	f[T] = 0;
	priority_queue<pair<int, int>> q;
	q.push(make_pair(0, T));
	while (q.size())
	{
		pair<int, int> t = q.top();
		q.pop();
		int u = t.second;
		if (vis[ u])
			continue;
		vis[ u] = True; // 第一次出队时最小
		for (int i = rh[ u]; i; i = ne[i])
		{
			int v = to[i];
			if (f[v] > f[ u] + w[i])
			{
				f[v] = f[ u] + w[i]; // 估价函数
				q.push(make_pair(-f[v], v));
			}
		}
	}
}
int aStar()
{
	priority_queue<node> q; // 优先队列
	node a = {f[S], S, 0};
	q.push(a);
	while (q.size())
	{
		node t = q.top();
		q.pop();
		int u = t.v;
		cnt[ u]++; // 记录出队次数
		if (cnt[T] == K)
			return t.d; // 边界
		for (int i = h[ u]; i; i = ne[i])
		{
			int v = to[i], d = t.d + w[i];
			if (cnt[v] < K)
			{
				node a = {d + f[v], v, d};
				q.push(a);
			}
		}
	}
	return -1;
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++)
	{
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		add(h, a, b, c);
		add(rh, b, a, c); // 反图
	}
	scanf("%d%d%d", &S, &T, &K);
	if (S == T)
		K++; // 重合点，0是第一条
	dijkstra();
	printf("%d\n", aStar());
}

B27 A*算法 第K短路

#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

const int N = 1010, M = 200010;
int h[N], rh[N], to[M], w[M], ne[M], tot;
void add(int h[], int a, int b, int c)
{
	to[++tot] = b;
	w[tot] = c;
	ne[tot] = h[a], h[a] = tot;
}
int n, m, S, T, K;
int f[N], vis[N], cnt[N];
struct node
{
	int s, v, d; // s排序，v点，d距离
	bool operator<(const node &x) const
	{
		return s > x.s;
	}
};

void dijkstra()
{
	memset(f, 0x3f, sizeof f);
	f[T] = 0;
	priority_queue<pair<int, int>> q;
	q.push(make_pair(0, T));
	while (q.size())
	{
		pair<int, int> t = q.top();
		q.pop();
		int u = t.second;
		if (vis[ u])
			continue;
		vis[ u] = True; // 第一次出队时最小
		for (int i = rh[ u]; i; i = ne[i])
		{
			int v = to[i];
			if (f[v] > f[ u] + w[i])
			{
				f[v] = f[ u] + w[i]; // 估价函数
				q.push(make_pair(-f[v], v));
			}
		}
	}
}
int aStar()
{
	priority_queue<node> q; // 优先队列
	node a = {f[S], S, 0};
	q.push(a);
	while (q.size())
	{
		node t = q.top();
		q.pop();
		int u = t.v;
		cnt[ u]++; // 记录出队次数
		if (cnt[T] == K)
			return t.d; // 边界
		for (int i = h[ u]; i; i = ne[i])
		{
			int v = to[i], d = t.d + w[i];
			if (cnt[v] < K)
			{
				node a = {d + f[v], v, d};
				q.push(a);
			}
		}
	}
	return -1;
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++)
	{
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		add(h, a, b, c);
		add(rh, b, a, c); // 反图
	}
	scanf("%d%d%d", &S, &T, &K);
	if (S == T)
		K++; // 重合点，0是第一条
	dijkstra();
	printf("%d\n", aStar());
}