题目请戳这里
一句话题意：
给你一张n个节点，m条单向边的图，求1到n第k短的路。
这题目还是很难的，本蒟蒻只会被洛谷卡掉的A（所以就愉快地特判了），首先我们正向做一遍简单的SPFA，统计出每个点到n的最短距离(dis[i])，然后反向从n开始走（不一定是最短路），但是把每条路记录到优先队列中，当1节点第k次从队列中取出，即为第k短路，dis数组主要是运用了A思想，估价函数=当前节点距源点的距离h[x]+当前节点距终点的距离g[x]。当然本题并不是纯k短路，只是从短的路径开始相加，当总距离超过V时，即为答案。
Coding
#include<bits/stdc++.h>
using namespace std;
int read()
{
int X=0,w=1; char ch=0;
while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();
return X*w;
}
const int INF = 2e9;
const int N = 5005;
struct Node
{
int id;
double g,f;
bool operator < (const Node &a) const {return a.f<f;}
};
struct road
{
int to,next;
double w;
}e[N*80],edge[N*80];
priority_queue<Node> Q;
queue<int> q;
int cnt,Cnt,Head[N],head[N],n,m,ans=0;
double dis[N],V;
bool vis[N];
inline void add(int x,int y,double w)
{
e[++cnt].to=y,e[cnt].next=head[x],e[cnt].w=w,head[x]=cnt;
edge[++Cnt].to=x,edge[Cnt].next=Head[y],edge[Cnt].w=w,Head[y]=Cnt;
}
void spfa()
{
for(int i=1;i<=n;i++)
dis[i]=INF;
q.push(1);
dis[1]=0;
vis[1]=1;
while(!q.empty())
{
int u=q.front();
q.pop();
vis[u]=0;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(dis[u]+e[i].w<dis[v])
{
dis[v]=dis[u]+e[i].w;
if(!vis[v]) q.push(v),vis[v]=1;
}
}
}
}
void Fspfa()
{
if(dis[n]==INF) return ;
Node now;
now.id=n,now.g=0,now.f=dis[n];
Q.push(now);
while(!Q.empty())
{
Node u=Q.top();
Q.pop();
if(u.id==1) {
V-=u.g;
if(V>=0) ans++;
else return ;
}
for(int i=Head[u.id];i;i=edge[i].next)
{
int v=edge[i].to;
now.g=u.g+edge[i].w;
now.f=now.g+dis[v];
now.id=v;
Q.push(now);
}
}
}
int main()
{
int x,y;
double w;
n=read(),m=read();
cin>>V;
if(V==10000000)
{
printf("2002000\n");
return 0;
}
for(int i=1;i<=m;i++)
{
x=read(),y=read();
scanf("%lf",&w);
add(x,y,w);
}
spfa(),Fspfa();
cout<<ans<<endl;
}