題目
題意:求 點s 到 點t 的 第 k 短 路的距離;
估價函數=目前值+目前位置到終點的距離
f(n)=g(n)+h(n); g(n)表示g目前從s到p所走的路徑的長度, h(n)‘啟發式函數’,表示為終點t到其餘一點p的路徑長度;
(1)将有向圖的所有邊反向,以原終點t為源點,求解t到所有點的最短距離;
(2)建立一個優先隊列,将源點s加入到隊列中;
(3)從優先級隊列中彈出f(p)最小的點p,如果點p就是t,則計算t出隊的次數;
如果目前為t的第k次出隊,則目前路徑的長度就是s到t的第k短路的長度,算法結束;
否則周遊與p相連的所有的邊,将擴充出的到p的鄰接點資訊加入到優先級隊列;
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
const int Maxn = 10010;
const int INF = 1e9;
struct node{
int to,val;
node(){}
node(int a,int b)
{
to = a; val = b;
}
};
vector<node> adj[Maxn],_adj[Maxn];
int n,m,k;
bool vis[Maxn];
int dis[Maxn];
void AddEdge(int x,int y,int val)
{
adj[x].push_back(node(y,val));
_adj[y].push_back(node(x,val));//反向存圖
}
void Dijkstra(int s,int t)
{
priority_queue<int, vector<int>,greater<int> > q;
while(!q.empty()) q.pop();
for(int i=1;i<=n;i++)
vis[i]=false,dis[i]=INF;
vis[t]=true;dis[t]=0;q.push(t);
int u,len;
while(!q.empty())
{
u = q.top(); q.pop();
len = _adj[u].size();
for(int i=0;i<len;i++)
{
node v = _adj[u][i];
if(dis[v.to]>dis[u]+v.val)
{
dis[v.to]=dis[u]+v.val;
if(!vis[v.to])
{
q.push(v.to);
vis[v.to]=true;
}
}
}
vis[u]= false;
}
}
struct Anode{
int h,g,id;
Anode(int a,int b,int c){h=a;g=b;id=c;}
bool operator < (Anode a) const{
return h+g > a.h + a.g;
}
};
priority_queue<Anode> Q;
int Astar(int s,int t) //A*算法
{
while(!Q.empty()) Q.pop();
Q.push(Anode(0,dis[s],s));
int len,num;
num=0;
while(!Q.empty())
{
Anode u = Q.top();
Q.pop();
if(u.id==t) ++num;
if(num>=k) return u.h;
len = adj[u.id].size();
for(int i=0;i<len;i++)
{
node v = adj[u.id][i];
Q.push(Anode(u.h+v.val,dis[v.to],v.to));
}
}
return -1;
}
int main()
{
while(scanf("%d%d",&n,&m)!=-1)
{
for(int i=0;i<Maxn;i++)
adj[i].clear(),_adj[i].clear();
int x,y,v,s,t;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&v);
AddEdge(x,y,v);
}
scanf("%d%d%d",&s,&t,&k);
if(s==t) k++;
Dijkstra(s,t);
printf("%d\n",Astar(s,t));
}
return 0;
}
/*
2 2
1 2 5
2 1 4
1 2 2
*/