题目内容
给定一有向带权图，求从 n 到 1 的前 k 短路的长度
解题思路
求 k 短路的一个常用的方法是使用 A*，怎么求呢？
首先，预处理出所有点到 1 的最短距离（使用反向图跑最短路），然后从 n 开始进行广搜，只不过队列改为优先队列，估价方式为 f+dis[now] 小的先出队，其中 f 为已经走过的路，dis[now] 为 now 到 1 的最短距离，这样子进行估价可以使估的价一定小于等于实际代价。然后 A* 会根据估价从小到大依次进行扩展，最先进入到 1 号的就是最短路，随后次短路，第三短路。。。会依次进入到 1 号点，每次输出走过路径长即可。
#include <queue>
#include <cstdio>
#include <vector>
#include <cctype>
#include <utility>
#include <cstring>
typedef long long ll;
using namespace std;
const int maxn=1e3+5;
struct node
{
ll pos,f;
node(){}
node(int _p,int _f)
{
pos=_p;
f=_f;
}
};
struct edge
{
ll from,to,dist;
edge(){}
edge(ll u,ll v,ll w)
{
from=u;
to=v;
dist=w;
}
};
//快读省略
vector<edge> g1[maxn],g2[maxn];//g1存正向图，g2存反向图
ll dis[maxn],n,m,k;
bool vis[maxn];
bool operator<(const node &_a,const node &_b)
{
return _a.f+dis[_a.pos]>_b.f+dis[_b.pos];
}
void dijsktra()//反向跑dij获取每个点的距离
{
priority_queue<pair<ll,ll>, vector<pair<ll,ll> >,greater<pair<ll,ll> > > q;
memset(dis,0x3f,sizeof(vis));
dis[1]=0;
q.push(make_pair(0,1));
while(!q.empty())
{
int now=q.top().second;
q.pop();
if(!vis[now])
{
vis[now]=1;
for(auto &e:g2[now])
{
if(dis[e.to]>dis[now]+e.dist)
{
dis[e.to]=dis[now]+e.dist;
q.push(make_pair(dis[e.to],e.to));
}
}
}
}
return;
}
void astar()//开始A*
{
priority_queue<node> q;
q.push(node(n,0));
while(!q.empty())
{
ll now=q.top().pos,f=q.top().f;
q.pop();
if(now==1)//如果到终点了
{
printf("%lld\n",f);//直接输出
if(!(--k))//如果已经求完前k短路，结束
return;
}
else
for(auto i:g1[now])//然后就是扩展
q.push(node(i.to,i.dist+f));
}
while(k--)//如果还有没搞完的
printf("-1\n");
return;
}
inline void ins(ll u,ll v,ll w)
{
g1[u].push_back(edge(u,v,w));
g2[v].push_back(edge(v,u,w));
return;
}
int main()
{
n=read(),m=read(),k=read();
ll u,v,w;
for(int i=1;i<=m;i++)
{
u=read(),v=read(),w=read();
ins(u,v,w);
}
dijsktra();
astar();
return 0;
}