【图论】3.30学习记录 k短路（A*算法）

从最短路说起的k短路

3.26看了最短路和次短路。我们发现次短路实际上就是把最短路给破坏掉然后跑最短路...
那我想...是不是破坏(k-1)次就能得到k短路呢，很显然是的，但是复杂度比较高，（因为一次dij是 O(nlogn)级别的，次短路的话最坏要跑m次 当最短路有m条边的时候）
那么k比较大的时候就只能选择更加便捷的算法了

A star算法

这个算法属于搜索的一种（虽然一说到搜索就想到DFS和BFS）
和DFS、BFS不同的是，另两个是把所有的可能性都遍历一遍，这个是选择当前情况下最好的往下遍历（也是能把所有的可能性都遍历了，但是是从最好的开始）

核心式子：F(x)=G(x)+H(x)

H(x)是从当前状态到最终状态的预计花费
G(x)是指从初始状态到当前状态n的实际花费。
F(x)是从最初状态经过当前状态到最终状态的预计花费

何为当前情况下最好的：F(x)最小的
A star 算法的核心：求好H(x)函数

用A star 算法求解k短路

模板题：魔法猪学院
代入核心式子：

1. H函数为当前状态到终点的预计最短路————通过反向跑dij进行预处理
2. 模拟取F(x)最小的：优先队列模拟

code：

#include<bits/stdc++.h>
using namespace std;

// #define int long long
#define f first
#define s second

const int MAXN=5005;
const double inf=(1<<30);

double dist[MAXN];
int vis[MAXN];
int n,m;
double tt;

struct edge{
	int v;
	double dis;
	bool operator < (const edge &x)const{
		return dis>x.dis;
	}
};
struct statue{
	double f,g;
	int pos;
	friend bool operator < (const statue &x,const statue &y){
		return x.f>y.f;
	}
};

vector<pair<int,double> >e[MAXN],ee[MAXN];

priority_queue<edge>pq;
void dij(){
	for(int i=1;i<=n;i++){
		dist[i]=inf;
		vis[i]=0;
	}
	dist[n]=0;
	pq.push({n,dist[n]});
	while(!pq.empty()){
		auto j=pq.top();
		pq.pop();
		int u=j.v;
		if(vis[u])continue;
		vis[u]=1;
		for(auto i:ee[u]){
			int v=i.f;double w=i.s;
			if(dist[u]+w<dist[v]){
				dist[v]=dist[u]+w;
				if(!vis[v])pq.push({v,dist[v]});
			}
		}
	}
}
priority_queue<statue>pqq;
int ans=0;
void a_star(){
	statue p,m;
	p.pos=1,p.g=0,p.f=dist[1];
	pqq.push(p);
	while(!pqq.empty()){
		auto p=pqq.top();
		pqq.pop();
		int x=p.pos;
		if(x==n){
			if(tt>=p.f){
				ans++;
				tt-=p.f;
			}
			else return;
		}
		for(auto i:e[x]){
			int v=i.f;double w=i.s;
			m.pos=v,m.g=w+p.g;
			m.f=m.g+dist[v];
			pqq.push(m);
		}
	}
}

signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>m>>tt;
	int u,v;double w;
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		e[u].push_back({v,w});
		ee[v].push_back({u,w});
	}
	dij();
	// for(int i=1;i<=n;i++){
	// 	cerr<<dist[i]<<" \n"[i==n];
	// }
	a_star();
	cout<<ans<<endl;
	// cerr<<tt<<endl;
}