求助

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#define int long long
using namespace std;
const int N = 1e4+5;
const int M = 5e4+5;
const int INF = 1e9;
struct Node{
	int to, w;
};
vector<Node> G[M];
bool vis[N]; 
int n, m, t, ans;
int dis[N], sum, a[N], f[N];

void dij(){
	for(int i = 1; i <= n; i++)
		dis[i] = INF, vis[i] = 0;
	priority_queue<Node, vector<Node>, greater<Node>> q;
	q.push({0, 1});
	dis[1] = 0;
	while(!q.empty()){
		int t = q.front().to;
		q.pop();
		if(vis[t])
			continue; 
		vis[t] = 1;
		for(int i = 0; i < G[t].size(); i++){
			int p = G[t][i].to;
			if(dis[p] > dis[t] + G[t][i].w){
				dis[p] = dis[t] + G[t][i].w;
				f[p] = t;//记录走过的点 
				vis[p] = 1, q.push({p, dis[p]});
			}
			else if(dis[p] == dis[t] + G[t][i].w && f[p] > t) //字典序大 
				f[p] = t;//替换为小的字典序 
		}
	}
	return ;
}

void dfs(int x){
	for(int i = 0; i < G[x].size(); i++){
		dfs(G[x][i].to);
		dis[f[G[x][i].to]] += dis[G[x][i].to]; 
	}
	ans = max(ans, (dis[i]-t) * a[i]); 
	return ;
}
int main(){
	cin >> n >> m >> t;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	for(int i = 1; i <= m; i++){
		int u, v, w;
		cin >> u >> v >> w;
		G[u].push_back({v, w});
		G[v].push_back({u, w});
	}
	dij();
//	cout << sum << "\n";
	dfs(1);//重新搜索看奶牛走的路径 			
	cout << ans;
	return 0;
}