@[第114514恋厨](/user/147401)
86分，两个 MLE，您再改进下。注意加“//”的地方。
```cpp
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
using namespace std;
typedef pair<double,int> PII;
const int N=5010,M=2e5+10;
int n,m;
int h[N],e[M],ne[M],rh[N],re[M],rne[M],idx,ridx;
double w[M],rw[M];
void add(int a,int b,double c)
{
e[++idx]=b;
ne[idx]=h[a];
h[a]=idx;
w[idx]=c;
re[++ridx]=a;
rne[ridx]=rh[b];
////////////rh[a]=ridx;
rh[b] = ridx;
rw[ridx]=c;
}
double f[N];
bool v[N];
void spfa()
{
queue<int> q;
////////////memset(f,0x3f,sizeof(f));
////////////f是浮点数，不能使用memset来设置
for (int i = 0; i < n; i++) f[i] = 1e20;
v[n]=1;
q.push(n);
f[n]=0;
while(!q.empty())
{
int x=q.front();
q.pop();
v[x]=0;
for(int i=rh[x];i;i=rne[i])
if(f[re[i]]>f[x]+rw[i])
{
f[re[i]]=f[x]+rw[i];
////////////注意SPFA算法的实现
if(!v[re[i]])
{
q.push(re[i]);
v[re[i]]=1;
}
}
}
}
int num[N],ans;
double maxw,dist[N];
void Astar(int k)
{
priority_queue<PII,vector<PII>,greater<PII> >heap;
heap.push({f[1],1});
while(!heap.empty())
{
int x=heap.top().second;
dist[x]=heap.top().first-f[x];
heap.pop();
if(dist[x]+f[x]>maxw) return;
num[x]++;
if(x==n)
{
ans++;
maxw-=dist[n];
continue;
}
if(num[x]>k) continue;
for(int i=h[x];i;i=ne[i])
if(num[e[i]]<k)
heap.push({dist[x]+w[i]+f[e[i]],e[i]});
}
}
signed main() {
cin>>n>>m>>maxw;
for(int i=1;i<=m;i++)
{
int x,y;
double z;
cin>>x>>y>>z;
add(x,y,z);
}
spfa();
Astar(maxw/f[1]);
cout<<ans<<endl;
}
```
by metaphysis @ 2021-04-02 11:04:53
@[metaphysis](/user/333388) 谢谢大佬%%%
by koishi_offical @ 2021-04-02 12:19:46
改进不出来了（悲）
by koishi_offical @ 2021-04-02 13:17:46