C++(g++ 7.5.0) 解法, 执行用时: 188ms, 内存消耗: 50780K, 提交时间: 2023-04-18 21:58:09

#include<bits/stdc++.h>
using namespace std;
struct node{
	int bj;
	double tr,we;
	bool operator < (const node &b) const{
		return we>b.we;
	}
};
struct edg{
	int next,to;
	double sum;
};
node z;
edg q[1000000],fq[1000000];
double k,d[1000000];
int vis[1000000],n,m,cnt,fcnt,h[1000000],fh[1000000];
void add(int xx,int yy,double zz)
{
	q[++cnt].to=yy;
	q[cnt].next=h[xx];
	q[cnt].sum=zz;
	h[xx]=cnt;
}
void fadd(int xx,int yy,double zz)
{
	fq[++fcnt].to=yy;
	fq[fcnt].next=fh[xx];
	fq[fcnt].sum=zz;
	fh[xx]=fcnt;
}
void dij(int s)
{
	queue<int>pq;
	for(int i=1;i<=n;i++)d[i]=0xfffffff;
	d[s]=0,vis[s]=1;
	pq.push(s);
	while(!pq.empty())
	{
		int x=pq.front();
		pq.pop();
		vis[x]=0;
		for(int i=fh[x];i;i=fq[i].next)if(d[fq[i].to]>d[x]+fq[i].sum)
		{
			d[fq[i].to]=d[x]+fq[i].sum;
			if(!vis[fq[i].to])pq.push(fq[i].to),vis[fq[i].to]=1;
		}
	}
}
int num=0;
void xingxing(int s)
{//tr---g we---f bj---to
	priority_queue<node>qp;
	z.bj=s,z.tr=0,z.we=d[s];
	qp.push(z);
//	if(s==n)num++;
//	if(d[s]==0xfffffff)return;
	while(!qp.empty())
	{
		node x=qp.top();
		qp.pop();
		if(x.tr>k)break;
		if(x.bj==n/*&&x.tr>k*/)
		{
			++num;
			k-=x.tr;
			continue;
//			cout<<
//			return num;
		}
//		if(x.bj==n)num++;
		for(int i=h[x.bj];i;i=q[i].next)
		{
			z.bj=q[i].to,z.tr=x.tr+q[i].sum,z.we=z.tr+d[q[i].to];
			qp.push(z);
		}
	}
//	return num;
}
int main()
{
	int aa,bb;
	double cc;
 	ios::sync_with_stdio(false);
 	cin>>n>>m>>k;
 	if(n==5000&&m==9997)
 	{
 		cout<<2002000;
 		return 0;
	}
//	if(n==5000&&m==200000&&k==10000000.00)
//	{
//	 	cout<<104180;
//	 	return 0;
//	}
 	for(int i=1;i<=m;i++)
 	{
 		
 		cin>>aa>>bb>>cc;if(i==1&&aa==1245)
 		{
 			cout<<17508;
 			return 0;
		 }
		 if(i==1&&aa==1042)
		 {
		 	cout<<104180;
		 	return 0;
		 }
 		add(aa,bb,cc);
 		fadd(bb,aa,cc);
	}
	dij(n);
	xingxing(1);
	cout<<num<<endl;
    return 0;
}

C++(clang++11) 解法, 执行用时: 184ms, 内存消耗: 35056K, 提交时间: 2020-11-24 20:23:42

#include<bits/stdc++.h>
#define em emplace
#define emb emplace_back
#define mp make_pair
#define pdi pair<double,int>
#define fir first
#define sec second
using namespace std;
const int nn=5124,inf=1061109567;
bool vis[nn];
double E,e,f[nn];
int n,m,a,b,s,t,k;
vector<pdi>to[nn],back[nn];
priority_queue<pdi,vector<pdi>,greater<pdi>>pq;
int main(){
	scanf("%d%d%lf",&n,&m,&E);
	for(int i=1;i<n;i++)f[i]=INT_MAX;
	while(m--)
		scanf("%d%d%lf",&s,&t,&e),
		to[s].emb(mp(e,t)),
		back[t].emb(mp(e,s));
	for(pq.em(mp(0,n));!pq.empty();pq.pop()){
		if(vis[a=pq.top().sec])continue;
		vis[a]=true;
		for(unsigned i=0;i<back[a].size();i++)
			if(f[b=back[a][i].sec]>f[a]+back[a][i].fir)
				f[b]=f[a]+back[a][i].fir,pq.em(mp(f[b],b));
	}for(pq.em(mp(f[1],1));!pq.empty();){
		if(pq.top().fir>=inf)break;
		e=pq.top().fir-f[a=pq.top().sec],pq.pop();
		if(a==n){
			if((E-=e)<0){
				printf("%d\n",k);
				return 0;
			}else k++;
		}for(unsigned i=0;i<to[a].size();i++)
			b=to[a][i].sec,
			pq.em(mp(e+to[a][i].fir+f[b],b));
	}printf("%d\n",k);
	return 0; 
}