题目：P2901 思路：先求出反向最短路（1开始），作为估值函数，然后A*搜索 代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cctype>
#include<vector>
#include<fstream>
using namespace std;
const int maxn = 1005;
const int INF = 0X3F;
typedef pair<int, int>PP;
int N, M, K;
int G[maxn][maxn];
int dis[maxn];
int vis[maxn];
//int ans[maxn];

struct cmp1 {
	bool operator()(PP& a, PP& b)
	{
		return a.second > b.second;
	}
};

struct cmp2 {
	bool operator()(PP& a, PP& b)
	{
		return a.second + dis[a.first] > b.second + dis[b.first];
	}
};
//Dijkstra和SPFA计算反向最短路，用作估值
void Dijkstra()
{
	memset(dis, INF, sizeof(dis));

	priority_queue<PP, vector<PP>, cmp1>Q;
	Q.push(PP(1, 0));
	dis[1] = 0;
	while (!Q.empty())
	{
		PP now = Q.top();
		Q.pop();

		if (vis[now.first])
			continue;

		vis[now.first] = 1;
		for (int i = 1; i <= N; i++)
		{
			if (G[i][now.first]) //反向
			{
				if (dis[i] > dis[now.first] + G[i][now.first])
				{
					dis[i] = dis[now.first] + G[i][now.first];
					PP next(i, dis[i]);
					Q.push(next);
				}
			}
		}
	}
}

void SPFA()
{
	memset(dis, INF, sizeof(dis));

	dis[1] = 0;
	vis[1] = 1;
	queue<int> Q;
	Q.push(1);
	while (Q.size())
	{
		int now = Q.front();
		Q.pop();

		vis[now] = 0;
		for (int i = 1; i <= N; i++)//向外发散 
		{
			if (G[i][now])
			{
				if (dis[now] + G[i][now] < dis[i])
				{
					dis[i] = dis[now] + G[i][now];
					if (!vis[i])
						Q.push(i), vis[i] = 1; //不在队列中，那就放进去更新别的点 
				}
			}
		}
	}
}
//A*搜索K短路
void Astar()
{
	//memset(vis, 0, (N + 1) * sizeof(int));
	priority_queue<PP, vector<PP>, cmp2>Q;
	Q.push(PP(N, 0));
	//vis[N] = 1;
	int pre = 0;
	int cnt = 0;
	while (!Q.empty())
	{		
		PP now = Q.top();
		Q.pop();

		//if (now.first == 1)
		//{			
		//	if (cnt >= K && pre != now.second)
		//		break;
		//	/*if (now.second != ans[cnt])
		//		printf("%d\n", cnt);*/
		//	printf("%d\n", now.second);
		//	pre = now.second;
		//	cnt++;
		//}

		for (int i = 1; i <= N; i++)
		{
			//if (vis[i]) continue;
			if (G[now.first][i])
			{
				//vis[i] = 1;
				PP next(i, now.second + G[now.first][i]);
				Q.push(next);
				//输出K个答案
				if (i == 1)
				{
					if (cnt >= K && pre != next.second)
						break;
					/*if (next.second != ans[cnt])
						printf("%d\n", cnt);*/
					printf("%d\n", next.second);
					pre = next.second;
					cnt++;
				}
			}
		}
	}
	//不够补-1
	if (cnt < K)
	{
		for (int i = cnt + 1; i <= K; i++)
			printf("-1\n");
	}
}

int main()
{
	//输入
	ifstream InFile("D:\\洛谷数据\\P2901_2.in", ios::in);
	//ifstream OutFile("D:\\洛谷数据\\P2901_2.out", ios::in);
	InFile >> N >> M >> K;
	//cin >> N >> M >> K;
	int x, y, d;
	for (int i = 1; i <= M; i++)
	{
		InFile >> x >> y >> d;
		//cin >> x >> y >> d;
		G[x][y] = d; //有向图 x->y = d
	}
	//输入结束
	InFile.close();
	//OutFile.close();

	/*int w, cur = 0;
	while (OutFile >> w)
		ans[cur++] = w;*/

	//开始搜索
	Dijkstra();
	//SPFA();
	Astar();
	
	return 0;
}

问题：试了数据2，发现缺少了第27短路（1540176），但不知道问题出在哪里