考虑到这题是要求出有多少只奶牛经过改点，又在该图是正权的前提下。

靠近（最短路树）叶子的点 $dis$ 一定比他的祖先们大，那就按 $dis$ 排序，从大到小，递推到最短路的前缀，然后后面就一样了，请问是实现的不对，还是想法有 bug ?

先在这里谢谢了，毕竟大家都要复习qwq

#include"iostream"
#include"cstdio"
#include"cmath"
#include"queue"
using namespace std;

#define N 10005
#define M 50005
#define inf 0x7fffffff
#define read(x) scanf("%d",&x)

int n,m,u,v,w,t;
int we[N];
int dis[N],vis[N],lst[N];
struct node
{
	int to,nxt,w;
}e[M<<1];
int head[N],cnt=0;
int ans=0;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
priority_queue<pair<int,int> >qq;

void add(int u,int v,int w){e[++cnt].to=v,e[cnt].nxt=head[u],e[cnt].w=w;head[u]=cnt;}

void dij()
{
	while(!q.empty())
	{
		int u=q.top().second;
		q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=head[u];i;i=e[i].nxt)
		{
			int j=e[i].to;
			if(dis[j]>dis[u]+e[i].w)
			{
				lst[j]=u,dis[j]=dis[u]+e[i].w;
				q.push(make_pair(dis[j],j));
			}
			else if(dis[j]==dis[u]+e[i].w&&lst[j]>u) lst[j]=u;
		}
	}
	return;
}

void work()
{
	while(!qq.empty())
	{
		int u=qq.top().second;
		qq.pop();
		we[lst[u]]+=we[u];
	}
	return;
}

int main()
{
	read(n),read(m),read(t);
	for(int i=1;i<=n;i++) read(we[i]);
	for(int i=1;i<=m;i++)
	{
		read(u),read(v),read(w);
		add(u,v,w),add(v,u,w);
	}
	for(int i=1;i<=n;i++) dis[i]=inf;
	dis[1]=0,q.push(make_pair(0,1));
	dij();
	for(int i=1;i<=n;i++) qq.push(make_pair(dis[i],i));
	work();
	for(int i=1;i<=n;i++)
	{
		if(t<dis[i]) ans=max(ans,(dis[i]-t)*we[i]);
	}
	printf("%d\n",ans);
	return 0;
}