Remmarguts‘ Date

题意：给定一个有向图，求起点s到终点t的第k短路的长度

分析：处理每个结点v到终点t的最短路径长度f【v】，做为估价函数，然后在反向图上跑以t为起点的最短路，这里估价函数值等于实际值。允许每个点最多入队k次。终点t第k次出队，对应距离d是第k短路的长度。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1010,M=200010;
int h[N],rh[N],to[M],w[M],ne[M],tot;
void add(int h[],int a,int b,int c){to[++tot]=b;w[tot]=c;ne[tot]=h[a],h[a]=tot;
}
int n,m,S,T,K;
int f[N],vis[N],cnt[N];
struct node{int s,v,d; //s排序，v点，d距离bool operator<(const node &x)const{return s>x.s;}
};void dijkstra(){memset(f,0x3f,sizeof f); f[T]=0; priority_queue<pair<int,int>> q;q.push(make_pair(0,T));while(q.size()){pair<int,int> t=q.top(); q.pop();int u=t.second;if(vis[u])continue;vis[u]=true; //第一次出队时最小for(int i=rh[u]; i; i=ne[i]){int v=to[i];if(f[v]>f[u]+w[i]){f[v]=f[u]+w[i]; //估价函数q.push(make_pair(-f[v],v));}}}
}
int aStar(){priority_queue<node> q; //优先队列node a={f[S],S,0}; q.push(a);while(q.size()){node t=q.top(); q.pop();int u=t.v;cnt[u]++; //记录出队次数if(cnt[T]==K) return t.d; //边界for(int i=h[u]; i; i=ne[i]){int v=to[i], d=t.d+w[i];if(cnt[v]<K){node a={d+f[v],v,d};q.push(a);}}}return -1;
}
int main(){scanf("%d%d",&n,&m);for(int i=1; i<=m; i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);add(h,a,b,c); add(rh,b,a,c); //反图}scanf("%d%d%d",&S,&T,&K);if(S==T) K++; //重合点，0是第一条dijkstra();printf("%d\n",aStar());
}