原題傳送門
先跑一遍最短路，求出
n
x
t
u
nxt_u
nxtu表示我下一步走到哪裡，然後跑一個拓撲
Code：
#include <bits/stdc++.h>
#define maxn 100010
#define LL long long
using namespace std;
struct heap{
int node;
LL len;
bool operator < (const heap &x) const{return x.len < len; }
};
priority_queue <heap> q;
queue <int> Q;
struct Edge{
int to, next, len;
}edge[maxn << 1];
int num, head[maxn], n, m, vis[maxn], nxt[maxn], deg[maxn];
LL dis[maxn], c[maxn], T, ans;
inline int read(){
int s = 0, w = 1;
char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
return s * w;
}
void addedge(int x, int y, int z){ edge[++num] = (Edge){y, head[x], z}, head[x] = num; }
int main(){
freopen("pc.in", "r", stdin);
freopen("pc.out", "w", stdout);
n = read(), m = read(), T = read();
for (int i = 1; i <= n; ++i) c[i] = read();
for (int i = 1; i <= m; ++i){
int x = read(), y = read(), z = read();
addedge(x, y, z), addedge(y, x, z);
}
for (int i = 2; i <= n; ++i) dis[i] = 1e11, nxt[i] = n + 1;
q.push((heap){1, 0});
while (!q.empty()){
heap tmp = q.top(); q.pop();
int u = tmp.node;
if (vis[u]) continue;
vis[u] = 1;
for (int i = head[u]; i; i = edge[i].next){
int v = edge[i].to, l = edge[i].len;
if (dis[v] > dis[u] + l){
dis[v] = dis[u] + l, nxt[v] = u;
if (!vis[v]) q.push((heap){v, dis[v]});
} else
if (dis[v] == dis[u] + l && u < nxt[v]){
nxt[v] = u;
if (!vis[v]) q.push((heap){v, dis[v]});
}
}
}
num = 0;
memset(head, 0, sizeof(head));
for (int i = n; i; --i) addedge(i, nxt[i], 0), ++deg[nxt[i]];
for (int i = 1; i <= n; ++i)
if (!deg[i]) Q.push(i);
while (!Q.empty()){
int u = Q.front(); Q.pop();
if (dis[u] > T) ans = max(ans, (dis[u] - T) * c[u]);
for (int i = head[u]; i; i = edge[i].next){
int v = edge[i].to;
--deg[v], c[v] += c[u];
if (!deg[v]) Q.push(v);
}
}
printf("%lld\n", ans);
return 0;
}