Description
找出1~k短路的长度。
Solution
k短路的求解要用到A*算法
A*算法的启发式函数f(n)=g(n)+h(n)
g(n)是状态空间中搜索到n所花的实际代价
h(n)是n到结束状态最佳路径的估计代价
关于h(n)的选取，当h(n)<实际代价时，搜索慢但可出解；h(n)=实际代价时，正确率与效率最高；h(n)>实际代价，快但只能得到近似解。
但在k短路问题中，h(n)是可以选到准确值的，就是n到结束节点的最短路，预处理时从结束节点做一次单源最短路即可。
按广搜的方式扩展节点，每次优先扩展f(n)最小的节点。
第i次扩展到目标节点，代表找到了第i短路。
正确性什么的很好理解。
k短路关于A*部分代码很简洁，用优先队列维护。
这道题就是裸题，但这道题很丧病地让proirity_queueMLE，于是要手写堆。
让我这个几乎没手写过堆的STL狗QwQ
Code
1 #include<cstdio>
2 #include<algorithm>
3 #include<queue>
4 #include<cstring>
5 using namespace std;
6 const int N=5e3+5,M=2e5+5;
7
8 double d[N];
9 int head[N],e[M],nxt[M],cnt;
10 double w[M];
11 int adde(int u,int v,double g){
12 e[++cnt]=v;w[cnt]=g;nxt[cnt]=head[u];head[u]=cnt;
13 }
14 int _head[N],_e[M],_nxt[M],_cnt;
15 double _w[M];
16 int _adde(int u,int v,double g){
17 _e[++_cnt]=v;_w[_cnt]=g;_nxt[_cnt]=_head[u];_head[u]=_cnt;
18 }
19 struct node{
20 double f,g;
21 int o;
22 bool operator<(const node&a)
23 const{return f<a.f;}
24 };
25 int n,m;
26 double c;
27
28 queue<int>q;
29 int inque[N];
30 int spfa(){
31 memset(d,127,sizeof(d));
32 d[n]=0;
33 inque[n]=1;
34 q.push(n);
35
36 while(!q.empty()){
37 int u=q.front();q.pop();
38 for(int i=_head[u];i;i=_nxt[i]){
39 int v=_e[i];
40 if(d[v]>d[u]+_w[i]){
41 d[v]=d[u]+_w[i];
42 if(!inque[v]){
43 q.push(v);
44 inque[v]=1;
45 }
46 }
47 }
48 inque[u]=0;
49 }
50 }
51
52 int ans,size;
53 node Q[2000000];
54 int push(node x){
55 int now,next;
56 Q[++size]=x;
57 now=size;
58 while(now>1){
59 next=now>>1;
60 if(Q[next]<Q[now]) break;
61 swap(Q[now],Q[next]);
62 now=next;
63 }
64 }
65 node pop(){
66 int now,next;
67 node ret;
68 ret=Q[1];
69 Q[1]=Q[size--];
70 now=1;
71 while((now<<1)<=size){
72 next=now<<1;
73 if(next<size&&Q[next+1]<Q[next]) next++;
74 if(Q[now]<Q[next]) break;
75 swap(Q[now],Q[next]);
76 now=next;
77 }
78 return ret;
79 }
80 void Astar(){
81 push((node){d[1],0,1});
82 while(size){
83 node x=pop();
84 for(int i=head[x.o];i;i=nxt[i]){
85 int v=e[i];
86 push((node){x.g+w[i]+d[v],x.g+w[i],v});
87 }
88 if(x.o==n){
89 c-=x.f;
90 if(c<0) return;
91 ans++;
92 }
93 }
94 }
95
96 int main(){
97 scanf("%d%d%lf",&n,&m,&c);
98 int u,v; double g;
99 for(int i=1;i<=m;i++){
100 scanf("%d%d%lf",&u,&v,&g);
101 adde(u,v,g);
102 _adde(v,u,g);
103 }
104
105 spfa();
106 Astar();
107
108 printf("%d\n",ans);
109 return 0;
110 }