标签：
写在前面学习算法的日子又到了~~
提供以下几种方法
暴搜
输出-1(是的，输出-1)
有算法的暴力
\(Dijkstra\)
\(Dijkstra\)的本质是贪心，复杂度为\(O(n^2)\)，堆优化后为\(O((m+n) \log (m+n))\)
\(SPFA\)
学长说最好不要用，因为它死了
\(A^\ast\)
\(y\)总有视频讲解，不懂的同学可以去看看，这里我就不再赘述了
下面直接进行\(A^\ast\)的讲解
所以，发现想出\(f\)很关键，,\(f\)要尽量大但不超过最优解
第几次出队就是第几短,于是终点出了\(k\)次就是第\(k\)短路了
按照\(Dijkstra\)的思想,我们每次取出\(d[x]+f[x]\) 最小的
然后更新所有能到达的点
发现\(f[x]\) 可以取到终点的距离,这样尽量大且一定比现在的解小
于是先倒着\(Dijkstra\)一遍(搞出\(f\))
然后\(A^ \ast\),直到终点第\(k\)次。
\(OK\),上代码
Code? Code1 //Dijstra 暴力版 const int maxx=1001; struct Node{ int v,to,next; }e[maxn<<1]; int head[maxx],dis[maxx]; int len,tot,n,m,v,S,T,K; bool vis[maxn]; priority_queue<pair<int,int> >q; inline void add(int x,int y,int z){ e[++tot].v=y; e[tot].to=z; e[tot].next=head[x]; head[x]=tot; } inline bool dfs(int x){ if(x==T) return true; vis[x]=true; for(int i=head[x];i;i=e[i].next){ int y=e[i].v; if(!vis[y]) if(dfs(y)==true) return true; } return false; } inline void dijkstra(){ if(!dfs(S)){puts("-1");return;} q.push(make_pair(0,S)); if(S==T) v=-1; while(q.size()){ int d=q.top().first,x=q.top().second; q.pop(); if(x==T){ if(++v==K){printf("%d",-d);return;} len=0; } else if(++len==maxx*15)break;//防止搜过多 for(int i=head[x];i;i=e[i].next){ int y=e[i].v; q.push(make_pair(d-e[i].to,y)); } } puts("-1"); } signed main(){ n=read(); m=read(); for(int i=1;i<=m;i++){ int x=read(),y=read(),z=read(); add(x,y,z); } S=read(); T=read(); K=read(); dijkstra(); return 0; } Code2 //Dijkstra + A* const int maxx=1001; struct Node{ int y,to,next; }e[maxn],e1[maxn]; int head[maxx],tot,head1[maxx],cnt;//head1为反向边 int n,m,dis[maxx],S,T,K,vis[maxx]; inline void add(int x,int y,int z){ e[++tot]=(Node){y,z,head[x]}; head[x]=tot; } inline void add1(int x,int y,int z){//反边 e1[++cnt]=(Node){y,z,head1[x]}; head1[x]=cnt; } priority_queue<pair<int,int> >q;//注意：这是大根堆 inline void dijkstra(){ mem(dis,0x3f); mem(vis,-1); dis[T]=0; q.push(make_pair(0,T)); while(q.size()){ int x=q.top().second;q.pop(); if(!vis[x])continue; vis[x]=0;//每个点只贡献一次 for(int i=head1[x];i;i=e1[i].next){ int y=e1[i].y; if(dis[y]>dis[x]+e1[i].to){ dis[y]=dis[x]+e1[i].to; q.push(make_pair(-dis[y],y)); } } } } inline void A_star(){ if(dis[S]==dis[0]){puts("-1");return;}//不连通 if(S==T) K++;//路径必须有边吧。 mem(vis,0); q.push(make_pair(-dis[S],S)); while(q.size()){ int x=q.top().second,d=-q.top().first-dis[x]; q.pop(); vis[x]++; if(vis[T]==K){printf("%d",d);return;} for(int i=head[x];i;i=e[i].next){ int y=e[i].y; if(vis[y]!=K)q.push(make_pair(-d-e[i].to-dis[y],y)); //重要剪枝——因为默认为大根堆并且每次取最小值，所以必须插入相反数或重载运算符。 } } puts("-1"); } signed main(){ n=read(); m=read(); for(int i=1;i<=m;i++){ int x=read(),y=read(),z=read(); add(x,y,z); add1(y,x,z); } S=read(); T=read(); K=read(); dijkstra();//跑反图，求出优秀的估价函数 A_star(); return 0; } Code3 //给出同学的 SPFA + A*,喜欢用spfa的同学可以看一眼 const int N=100010; int tot,tc,n,m,s,t,k,x,y,l; int lin[N],linc[N],vis[N],f[N]; struct gg { int x,y,next,v; }a[N],e[N]; struct node { int pos,f,dis; bool operator<(node a)const{ return a.f+a.dis<f+dis; } }; inline void add(int x,int y,int v) { a[++tot].y=y; a[tot].next=lin[x]; a[tot].v=v; lin[x]=tot; } inline void add_c(int x,int y,int v) { e[++tc].y=y; e[tc].next=linc[x]; e[tc].v=v; linc[x]=tc; } inline void spfa(int t) { queue<int> q; memset(f,0x3f,sizeof(f)); memset(vis,0,sizeof(vis)); q.push(t); f[t]=0; vis[t]=1; while(q.size()) { int x=q.front(); q.pop(); vis[x]=0; for(int i=lin[x];i;i=a[i].next) { int y=a[i].y; if(f[y]>f[x]+a[i].v) { f[y]=f[x]+a[i].v; if(!vis[y]) { vis[y]=1; q.push(y); } } } } } priority_queue<node>q; inline int astar() { if(f[s]==0x3f) return -1; int ts[N]; memset(ts,0,sizeof(ts)); node tmp,h; h.pos=s; h.f=0; h.dis=0; q.push(h); while(q.size()) { node x=q.top(); q.pop(); ts[x.pos]++; if(ts[x.pos]==k&&x.pos==t) return x.dis; if(ts[x.pos]>k) continue; for(int i=linc[x.pos];i;i=e[i].next) { tmp.pos=e[i].y; tmp.f=f[e[i].y]; tmp.dis=x.dis+e[i].v; q.push(tmp); } } return -1; } int main() { read(n); read(m); if(m==0) {cout<<"-1"<<endl; return 0;} for(int i=1;i<=m;i++) { read(x); read(y); read(l); add(y,x,l); add_c(x,y,l); } read(s); read(t); read(k); if(s==t)++k; spfa(t); cout<<astar()<<endl; return 0; }\[ The \quad End \]
\[ \text{从白云看到,不见蓝天；从风雨寻回,梦的起点。-《梦想天空分外蓝》陈奕迅} \]
? Acwing 178 && POJ 2449 ?
标签：
原文地址：https://www.cnblogs.com/cbyyc/p/11601316.html