昨晚看WC论文发现自己连K短路的经典A*算法还不会，补了一波，模板题输出-1后没return继续跑wa了一早上......
算法流程：
①在反向图中求出t到每个点的最短路
②从原点bfs，估价f=d+dis[x]，即当前已走的路径长度+最短路径
③遇到第k次汇点就是答案
据说这复杂度是O(n*k)的....不会证.....
代码：
#include<algorithm> #include<iostream> #include<cstdlib> #include<cstring> #include<cstdio> #include<cmath> #include<queue> #define inf 1<<29 #define M 500200 #define N 500020 using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,k,s,t; int head[N],pos; int head1[N],pos1; struct edge{int to,c,next;}ee[M<<1],e[M<<1]; void add(int a,int b,int c) {pos++;e[pos].to=b,e[pos].c=c,e[pos].next=head[a],head[a]=pos;} void add1(int b,int a,int c) {pos1++;ee[pos1].to=b,ee[pos1].c=c,ee[pos1].next=head1[a],head1[a]=pos1;} queue<int>Q;bool vis[N];int dis[N]; void spfa(int st) { for(int i=1;i<=n;i++) dis[i]=inf,vis[i]=0; dis[st]=0,vis[st]=1;Q.push(st); while(!Q.empty()) { int u=Q.front();Q.pop();vis[u]=0; for(int i=head1[u];i;i=ee[i].next) { int v=ee[i].to; if(dis[v]>dis[u]+ee[i].c) { dis[v]=dis[u]+ee[i].c; if(!vis[v])Q.push(v),vis[v]=1; } } } } struct node{int x,d,f;}u,v; bool operator < (node a,node b) { if(a.f!=b.f)return a.f>b.f; } priority_queue<node>que; void solve() { while(!que.empty())que.pop(); if(dis[s]==inf) { printf("-1\n"); return ; } u.f=dis[s],u.x=s,u.d=0; int now=0;que.push(u); while(!que.empty()) { u=que.top();que.pop(); if(u.x==t) now++; if(now==k) { printf("%d\n",u.d); return; } for(int i=head[u.x];i;i=e[i].next) { int tc=e[i].to;v=u; v.x=tc,v.d+=e[i].c; v.f=dis[v.x]+v.d; que.push(v); } }printf("-1\n"); } int main() { // freopen("a.in","r",stdin); // freopen("a.out","w",stdout); while(~scanf("%d%d",&n,&m)) { memset(head,0,sizeof(head)); memset(head1,0,sizeof(head1)); pos1=pos=0; for(int i=1;i<=m;i++) { int x=read(),y=read(); int c=read(); add(x,y,c); add1(x,y,c); }s=read(),t=read(),k=read(); if(s==t)k++; spfa(t);solve(); } }
