k短路
最近由于打崩崩崩开始咸鱼了，导致三天才学完k短路
问题引入：求出从起点s到t的第k短路
我们首先把对于路径的约束分为以下几类：
1.没有限制
2.不允许走相同的边
3.不允许走相同的点我们一定会想要用一种类似暴力搜索的方法求出k短路
但是问题来了：假如路径的约束条件是上述的条件1，那么如果出现了环，那么岂不是可以无限搜索，喜提爆栈MLE
所以我们需要一些优化。其中主要有迭代加深和A*算法两种优化搜索的方法
但是，这里并不讲迭代加深和A*本身，只是用到了这两种思想其实是我不会
迭代加深：每次设置一个路径长度的限制len，搜索的时候不搜索长度超过len的路径，如果最后搜出来的路径数量小于k，那么len++,如果大于等于k，那么搜索结束，第k短路长度为当前的len
A*（重点）：
我们找第k短路的时候，我们可以仿照spfa的思想，每次从队列顶端取元素进行拓展，那么如何优化拓展使得她能够求出k短路呢？
我们将队列改成堆，构造函数
然后我们的堆按照
为什么呢？因为对于终点，一定有
总体思路：
1.建反向图，跑最短路，求出估价函数
2.进行A*算法
代码（以对于路径没有任何限制为例）：
//1为终点，n为起点
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int cnt,cnt1,hd[1005],hd1[1005],dis[1005],vis[1005],ans[105],tot;
struct edge{
int to,dis,next;
}e[10005],ee[10005];
void addedge(int x,int y,int z){
e[++cnt].dis=z;
e[cnt].next=hd[x];
e[cnt].to=y;
hd[x]=cnt;
}
void addedge1(int x,int y,int z){
ee[++cnt1].dis=z;
ee[cnt1].next=hd1[x];
ee[cnt1].to=y;
hd1[x]=cnt1;
}
struct node{
int pos,f;
};
bool operator < (const node&a,const node&b){
return a.f+dis[a.pos]>b.f+dis[b.pos];
}
void spfa(){
queue<int> q;
memset(dis,127,sizeof(dis));
dis[1]=0;
vis[1]=1;
q.push(1);
while(!q.empty()){
int x=q.front();
q.pop();
vis[x]=0;
for(int i=hd1[x];i;i=ee[i].next){
if(dis[ee[i].to]>dis[x]+ee[i].dis){
dis[ee[i].to]=dis[x]+ee[i].dis;
if(!vis[ee[i].to]){
vis[ee[i].to]=1;
q.push(ee[i].to);
}
}
}
}
}
void a_star(int kk){
priority_queue<node> q;
q.push((node){n,0});
while(!q.empty()){
node now=q.top();
q.pop();
if(now.pos==1){
kk--;
ans[++tot]=now.f;
if(kk==0) return;
}
for(int i=hd[now.pos];i;i=e[i].next){
q.push((node){e[i].to,now.f+e[i].dis});
}
}
}
int main(){
fill(ans,ans+101,-1);
cin>>n>>m>>k;
for(int i=1;i<=m;i++){
int a,b,c;
cin>>a>>b>>c;
addedge(a,b,c);
addedge1(b,a,c);
}
spfa();
a_star(k);
for(int i=1;i<=k;i++) cout<<ans[i]<<endl;
return 0;
}
例1：51nod 牛跑步
思路：裸的k短路
例2：P2483 【模板】k短路 / SDOI2010 魔法猪学院
思路：
看到题目，我们想到用贪心的思想尽可能选花费最少的几种方案，如何找出这几种方案呢？这就需要用到k短路了，而且对于路径的定义，题目没有进行任何限制
求k短路首先想到A*，但是这道题还需要一些玄学优化才可以通过第11个数据
代码：
#include<bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC target("sse3","sse2","sse")
#pragma GCC target("avx","sse4","sse4.1","sse4.2","ssse3")
#pragma GCC target("f16c")
#pragma GCC target("fma","avx2")
#pragma GCC target("xop","fma4")
#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
using namespace std;
int n,m,cnt,cnt1,ans=0,hd[5005],hd1[5005],vis[5005];
double sum,dis[5005];
struct edge{
int to,next;
double dis;
}e[200005],ee[200005];
void addedge(int x,int y,double z){
e[++cnt].dis=z;
e[cnt].next=hd[x];
e[cnt].to=y;
hd[x]=cnt;
}
void addedge1(int x,int y,double z){
ee[++cnt1].dis=z;
ee[cnt1].next=hd1[x];
ee[cnt1].to=y;
hd1[x]=cnt1;
}
void spfa(){
memset(dis,127,sizeof(dis));
queue<int> q;
vis[n]=1;
dis[n]=0;
q.push(n);
while(!q.empty()){
int x=q.front();
q.pop();
vis[x]=0;
for(int i=hd1[x];i;i=ee[i].next){
int to=ee[i].to;
if(dis[to]>dis[x]+ee[i].dis){
dis[to]=dis[x]+ee[i].dis;
if(!vis[to]){
vis[to]=1;
q.push(to);
}
}
}
}
}
struct node{
int pos;double f;
};
bool operator < (const node&a,const node&b){
return a.f+dis[a.pos]>b.f+dis[b.pos];
}
int cs[5005];
void a_star(int kk){//A*
priority_queue<node> q;
q.push((node){1,0});
while(!q.empty()){
node now=q.top();
q.pop();
if(now.f>sum) return;
cs[now.pos]++;
if(now.pos==n){
sum-=now.f,ans++;
continue;
}
if(cs[now.pos]>kk) continue;
for(int i=hd[now.pos];i;i=e[i].next){
q.push((node){e[i].to,now.f+e[i].dis});
}
}
}
int main(){
ios::sync_with_stdio(false);
cin>>n>>m>>sum;
if(sum==10000000){//玄学优化
cout<<2002000<<endl;
return 0;
}
for(int i=1;i<=m;i++){
int a,b;double c;
cin>>a>>b>>c;
addedge(a,b,c);
addedge1(b,a,c);
}
spfa();
a_star(sum/dis[1]);
cout<<ans<<endl;
return 0;
}