RT，测试点2和13 MLE了

Code：

#include<cstdio>
#include<algorithm>
#include<queue>
#include<iostream>
#include<cstring>
#include<ctime>
#include<cmath>
using namespace std;
#define maxn 5005
#define maxm 200004
struct aaa {
    int to,nxt;
    double w;
}a[maxm],b[maxm];
int tot,head[maxn],Tot,Head[maxn],n,m,k;
struct node {
    int u;
    double val,f;
}now;
priority_queue<node> q;
bool operator < (node a,node b) {
    return a.f > b.f;
}
double dis[maxn];
bool vis[maxn];
const int inf=1e9+7;
void spfa() {
    for(int i=1;i<=n;i++) dis[i]=(double)inf;
    dis[n]=0;
    queue<int> s;
    s.push(n);
    while(s.size()) {
        int u=s.front();
        s.pop();
        vis[u]=false;
        for(int i=Head[u];i!=-1;i=b[i].nxt) {
            int v=b[i].to;
            if(dis[v] > dis[u] + b[i].w ) {
                dis[v]=dis[u]+b[i].w;
                if(!vis[v]) {
                    vis[v]=true;
                    s.push(v);
                }
            }
        }
    }
}
void add(int x,int y,double w) {
    a[tot].to=y;
    a[tot].w=w;
    a[tot].nxt=head[x];
    head[x]=tot++;
}
void Add(int x,int y,double w) {
    b[Tot].to=y;
    b[Tot].w=w;
    b[Tot].nxt=Head[x];
    Head[x]=Tot++;
}
double maxx;
int ans;
int num[maxn];
void Astar() {
    if(dis[1]==inf) return;
    now.u=1;
    now.val=0;
    now.f=dis[1];
    q.push(now);
    while(q.size()) {
        node u=q.top();
        q.pop();
        if(u.f > maxx) return;
        num[u.u]++;
        if(u.u==n) {
            maxx-=u.val;
            ans++;
            continue;
        }
        if(num[u.u] > k) continue;
        for(int i=head[u.u];i!=-1;i=a[i].nxt) {
            int v=a[i].to;
            double w=a[i].w;
            now.u=v;
            now.val=u.val+w;
            now.f=now.val+dis[v];
            q.push(now);
        }
    }
}
int main() { 
    int c1=clock();
#ifdef LOCAL
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
    //=========================================
     memset(head,-1,sizeof(head));
     memset(Head,-1,sizeof(Head));
     scanf("%d%d%lf",&n,&m,&maxx);
     for(int i=1;i<=m;i++) {
         int x,y;
         double w;
         scanf("%d%d%lf",&x,&y,&w);
         add(x,y,w);
         Add(y,x,w);
     }
     spfa();
    //  for(int i=1;i<=n;i++) printf("%lf",dis[i]);
     k=maxx/dis[1];
     Astar();
     printf("%d\n",ans);
    //=========================================
    cerr<<"Tmie Used:"<<clock()-c1<<"ms"<<endl;
    return 0;
}