第一场区域赛选拔赛的题目，虽然是板子题，但这个板子我是第一次敲......不仅板子是第一次敲，k短路也是第一次敲......
题意就是让你求一张图上从起点S到终点T的k短路。这里我们使用A*来进行求解。构造一个函数\(h[x] = f[x] + g[x]\)，其中f[x]表示当前搜索时的代价,也就是边权；g[x]表示的是从当前点到终点的最短路,这可以通过以T为起点反向dijkstra得到。对于终点T，当它第k次从队首中被拿出来时，说明此时已经找到了k短路。事实上这里的A*只是使用估价函数优化了的BFS，是简化了的A*，真正的A*还需要维护OpenList和CloseList两个集合。
代码如下：
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <utility>
#include <map>
#include <stack>
#include <cctype>
#include <string>
#include <queue>
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug printf("debug\n")
#define INF 0x3f3f3f3f
#define IOS std::ios::sync_with_stdio(false)
const int maxn=1e5+5;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
struct edge{
int u;
int v,c;
int nxt;
int nxt1;
edge(){}
edge(int u,int v,int c)
:u(u),v(v),c(c){
}
};
edge es[100005];
int head[1010];
int head1[1010];
int tot_e; //总边数
int st,ed,k;
int n,m;
int dis[maxn];
bool vis[maxn];
struct pro{
int v,c;
pro(){}
pro(int v,int c)
:v(v),c(c){
}
/*
h[x] = f[x] + g[x]
其中f[x]表示当前搜索时的代价,也就是边权
g[x]表示的是从当前点到终点的最短路,可以
反向跑一遍dij得到
*/
bool operator<(const pro& pa) const{
return c+dis[v]>pa.c+dis[pa.v]; //估价函数
}
};
void init()
{
mst(head,-1);mst(head1,-1);
tot_e=0;
}
void add(int u,int v,int c)
{
//链式前向星加边
es[tot_e]=edge(u,v,c);
es[tot_e].nxt=head[u];head[u]=tot_e;
es[tot_e].nxt1=head1[v];head1[v]=tot_e++;
}
priority_queue<pro> que;
void dijkstra(int start)
{
mst(vis,0);
for(int i=1;i<=n;i++) dis[i]=INF;
dis[start]=0;
while(!que.empty()) que.pop();
que.push(pro(start,0));
while(!que.empty()){
pro cur=que.top();
que.pop();
if(vis[cur.v]) continue;
vis[cur.v]=1;
for(int i=head1[cur.v];i!=-1;i=es[i].nxt1){
if(dis[es[i].u]>dis[cur.v]+es[i].c){
dis[es[i].u]=dis[cur.v]+es[i].c;
que.push(pro(es[i].u,0));
}
}
}
}
int Astar(int start) //其实这里只是经过了启发式优化的BFS
{
while(!que.empty()) que.pop();
que.push(pro(start,0));
while(!que.empty()){
pro cur=que.top();
que.pop();
if(cur.v==ed){
if(k>1) k--; //终点第k次入队时,说明找到了k短路
else return cur.c;
}
for(int i=head[cur.v];i!=-1;i=es[i].nxt)
que.push(pro(es[i].v,cur.c+es[i].c));
}
return -1;
}
int main()
{
while(scanf("%d %d",&n,&m)!=EOF){
init();
int u,v,c;
for(int i=0;i<m;i++){
scanf("%d %d %d",&u,&v,&c);
add(u,v,c);
}
scanf("%d %d %d",&st,&ed,&k);
dijkstra(ed);
if(dis[st]==INF){
printf("-1\n");
}else{
if(st==ed) k++;
int ans=Astar(st);
printf("%d\n",ans);
}
}
return 0;
}