题目链接
题意:
给你个图 让你求s到t的第k短路\
思路:
首先讲讲A*算法吧。众所周知，A*算法就是启发式搜索，基本形式就是这样:f(x)=g(x)+h(x);其中f(x)代表在x点所需要的总代
价，而g(x)代表：从源点到x点已经耗费的实际代价，h(x)代表从x到终点需要的估计代价，这个函数是一个估计值.而从x到终点真正需
要的代价为h*(x)，在整个启发式搜索中我们必须保证h(x)<=h*(x);不然的话会由于对当前的估价值过高，则会引起答案的错误。构建A*的
关键在于准确的规划一个h(x)函数，使得接近h*(x),这样的搜索会使得答案又快又准。可以想象h(x)过小会使得解空间过大，这样搜索出来
的结果会很准确但是速度太慢，而对h(x)的过高估计，即估计代价太大会使得结果不准确。
这样我们可以理解了BFS的搜索过程，BFS的搜索过程中没有考虑到h(x)的估计代价，也就是说h(x)=0,只考虑g(x)的实际代价。这样根
据实际代价来进行搜索，虽然可以说是很恶心的A*,同样地我们可以知道，BFS的解空间确实很大。
第一次写A*,目前只会应用在K短路上。不过也有点感觉了，关键在于h(x)的设计！
具体实现的话就是用优先队列每次取出估价函数最小的去扩展，这里的f（n）实际上就是代表了从s走到n后再从n走到t的距离.所以我们选取最小的 才能更快的去降低求解的范围提高求解速率,使其有方向的扩展.关于这里的h(n)我们用n到t的最短距离来表示,这个估计代价是准确的,我们反向建图跑一遍spfa求t到其余各个点的最短路.
我们开一个变量标记t出现了几次 出现了k次的时候 就是第k短路了
#include<stdio.h> #include<iostream> #include<queue> #include<vector> #include<string.h> #define PT printf #define SC scanf #define mod 99991 #define inf 0x3f3f3f3f using namespace std; const int maxn=1e3+10; const int mm=1e5+10; typedef long long ll; int n,m; int s,t,k; int dis[maxn]; int book[maxn]; struct node { int to; int cost; }; struct A { int f; int g; int v; friend bool operator<(A a,A b ) { if(a.f==b.f) return a.g>b.g; return a.f>b.f; } }; vector<node>edge[maxn],ff[maxn]; void spfa() { memset(dis,inf,sizeof(dis)); memset(book,0,sizeof(book)); dis[t]=0; book[t]=1; queue<int>qt; qt.push(t); while(!qt.empty()) { int w=qt.front(); qt.pop(); for(int i=0;i<ff[w].size();i++) { int tt=ff[w][i].to; if(dis[tt]>dis[w]+ff[w][i].cost) { dis[tt]=dis[w]+ff[w][i].cost; if(!book[tt]) { book[tt]=1; qt.push(tt); } } } book[w]=0; } return ; } int Astar() { priority_queue<A>Q; int time=0; if(dis[s]==inf) return -1; A x,y; x.v=s,x.g=0,x.f=dis[s]+x.g; Q.push(x); while(!Q.empty()) { y=Q.top(); Q.pop(); if(y.v==t) { time++; if(time==k) return y.g; } for(int i=0;i<edge[y.v].size();i++) { x.v=edge[y.v][i].to; x.g= y.g+edge[y.v][i].cost; x.f=x.g+dis[x.v]; Q.push(x); } } return -1; } int main() { int a,b; node c; scanf("%d %d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d %d %d",&a,&c.to,&c.cost); edge[a].push_back(c); b=c.to; c.to=a; ff[b].push_back(c); } scanf("%d %d %d",&s,&t,&k); if(s==t) k++; spfa(); printf("%d\n",Astar()); return 0; }
Marcus-Bao 认证博客专家 推荐系统 ACM算法竞赛 机器学习 本科毕业于国内知名四非大学，现中国科学院大学博士生，中国科学院计算技术研究所vipl实验室，老年ACM铁牌退役选手，喜欢算法竞赛，会点数据结构和算法，熟悉c++，python等；现阶段研究方向主要为机器学习与数据挖掘，比较关注推荐系统，发过顶会，炼过丹，平时博客主要记录些关于算法、数据结构，人工智能技术以及平时看的论文总结分享等，欢迎大家关注我，一起多多交流共同进步！
