dijkstra + A* 第k短路

Graph 圖論

第k短路

今天好懶啊，不想補了……但是怕忘了，先把筆記挂上日後補上吧（狗頭保命），但是啟發式搜尋的确挺有意思的一個算法。（一定補一定補）

感覺很好的一篇部落格，膜大佬 A*算法

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
int n,m,begin,end,k;
struct edge{
	int b;
	int cost;
};
vector<edge>map[1001];
struct infor{
	int num;
	int f;
	int g;
	int pre;
	friend bool operator < (infor a,infor b){
		if(a.f == b.f){
			if(a.g == b.g) return a.num > b.num;
			else return a.g > b.g;
		}
		else return a.f > b.f;
	}
};
int vis[1001];
int dist[1001];
int mp[1001][1001];
int flag[1001];

void dijkstra(int node){
	for(int i=1;i<=n;i++){
		if(vis[i]==0 && dist[i]>dist[node]+mp[node][i]){
			dist[i] = dist[node] + mp[node][i];
		}
	}
	int mini = -1;
	int Min = 0x7f7f7f7f;
	for(int i=0;i<n;i++){
		if(vis[i]==0 && dist[i]<Min){
			Min = dist[i];
			mini = i;
		}
	}
	if(mini == -1){
		return ;
	}
	else{
		vis[mini] = 1;
		dijkstra(mini);
	}
}
void Astar(){//f = g + dist
	memset(flag,0,sizeof(flag));
	priority_queue<infor>q;
	infor p;
	//起點入隊 
	p.num = begin;
	p.pre = -1;
	p.g = 0;
	p.f = dist[begin] + p.g;
	flag[begin] = 1;
	q.push(p);
	int cnt = 0;
	infor node;
	while(cnt<k && !q.empty()){
		node = q.top();//node是隊頭元素
		q.pop();
		for(int i=0;i<map[node.num].size();i++){
			edge e = map[node.num][i];
			p.num = e.b;
			p.pre = node.num;
			p.g = node.g + e.cost;
			p.f = p.g + dist[p.num];
			q.push(p);
		}
		if(node.num==end){
			cnt++;
		}
		//cout << node.pre << "->" << node.num << ":" << node.f << endl;
	}
	if(cnt==k) cout << node.f << endl;
	else cout << "No" << endl;
}
int main(){
	cin >> n >> m >> k >> begin >> end;
	memset(vis,0,sizeof(vis));
	memset(dist,0x7f7f7f7f,sizeof(dist));
	memset(mp,0x7f7f7f7f,sizeof(mp));
	for(int i=0;i<m;i++){
		int a,b,c;
		cin >> a >> b >> c;
		edge node;
		node.b = b;
		node.cost = c;
		map[a].push_back(node);
		mp[b][a] = c;
	}
	vis[end] = 1;
	dist[end] = 0;
	dijkstra(end);//反邊查找h(i);
	Astar();//啟發式搜尋
	return 0;
}