| Time Limit: 4000MS | Memory Limit: 65536K | |
| Total Submissions:35025 | Accepted: 9467 |
Description
Input
Output
Sample Input
2 2 1 2 5 2 1 4 1 2 2
Sample Output
14
思路
或许将其分在最短路不是特别合适，但是暂时就这样吧
此题为第k短路，用到了a*算法
这是一个神奇的算法。用它来求第k小的话，就是用它不断搜索，即使遇到了终点也不停止。
首先我们知道，这个东西本来就是求最短路的一个算法，所以第一次遇到终点，一定是最短路。遇到终点后，如果不停止，那么接下来，在优先队列里面第二靠近终点的肯定会及时补充上。总之，在这个算法里面，
没有vis数组的限制，又将耗费最小的放在前面，所以第二个到达终点的路径就是第二短的了。
或许这样太过于抽象，但是你只需要记住一点，那就是在这个题目里面的A*算法，它的估计值是精确的，因为我们估计值的来源，是对终点反向图的Dijkstra求出来的。正是这个原因，这个算法跑到的每一次终点
，都是准确的第几小。
代码
#include<iostream>
#include<vector>
#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;
const int inf = 2100000000;
vector<int>u[200024],w[200024];
vector<int>ux[200024],wx[200024];
bool book[200024];
int dis[200024];
int n,m,s,t,k;
struct node
{
int num;
int dis;
bool operator<(const node x)const
{
return dis>x.dis;
}
};
struct aa
{
int num;
int g,f;
bool operator<(const aa x)const
{
if(x.f==f){return x.g<g;}
return x.f<f;
}
};
void Dijkstra()
{
node exa;
fill(dis,dis+n+5,inf);
priority_queue<node>q;
q.push(node{t,0});
dis[t]=0;
while(!q.empty()){
exa=q.top();q.pop();
if(book[exa.num]){continue;}
book[exa.num]=true;
int siz=ux[exa.num].size();
for(int i=0;i<siz;i++){
if(dis[ux[exa.num][i]]>dis[exa.num]+wx[exa.num][i]){
dis[ux[exa.num][i]]=dis[exa.num]+wx[exa.num][i];
q.push(node{ux[exa.num][i],dis[ux[exa.num][i]]});
}
}
}
}
int A_star()
{
aa exa;
if(dis[s]==inf){return -1;}
priority_queue<aa>q;
int cnt = 0;
if(s==t){k++;}
int r,g,f;
g=0;f=g+dis[s];
q.push(aa{s,g,f});
while(!q.empty()){
exa= q.top();
q.pop();
r=exa.num;
if(r==t){cnt++;}
if(cnt==k){return exa.g;}
int siz=u[r].size();
for(int i=0;i<siz;i++){
g=exa.g+w[r][i];
f=g+dis[u[r][i]];
q.push(aa{u[r][i],g,f});
}
}
return -1;
}
int main()
{
scanf("%d%d",&n,&m);
int x,y,z;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&z);
u[x].push_back(y);
w[x].push_back(z);
ux[y].push_back(x);
wx[y].push_back(z);
}
scanf("%d%d%d",&s,&t,&k);
Dijkstra();
printf("%d\n",A_star());
return 0;
}
原文：https://www.cnblogs.com/ZGQblogs/p/9378909.html