ABC035 D問題（トレジャーハント）を解く

#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
#define INF (1LL << 60)
typedef pair<ll, int> P;
struct Edge {
	int to;
	ll weight;
	Edge() {}
	Edge(int t, ll w) : to(t), weight(w) {}
};

int main()
{
	int n, m;
	ll t;
	cin >> n >> m >> t;
	vector<ll> a(n + 1);
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
	}
	vector<vector<Edge>> G(n + 1), rG(n + 1);
	for (int i = 0; i < m; ++i) {
		int u, v;
		ll c;
		cin >> u >> v >> c;
		G[u].push_back(Edge(v, c));
		rG[v].push_back(Edge(u, c));
	}

	vector<ll> dist(n + 1, INF);
	priority_queue<P, vector<P>, greater<P>> que;
	dist[1] = 0;
	que.push(P(0, 1));
	while (!que.empty()) {
		P p = que.top();
		que.pop();
		int now = p.second;
		if (dist[now] < p.first) {
			continue;
		}
		for (auto next_v : G[now]) {
			if (dist[next_v.to] > dist[now] + next_v.weight) {
				dist[next_v.to] = dist[now] + next_v.weight;
				que.push(P(dist[next_v.to], next_v.to));
			}
		}
	}

	vector<ll> r_dist(n + 1, INF);
	r_dist[1] = 0;
	que.push(P(0, 1));
	while (!que.empty()) {
		P p = que.top();
		que.pop();
		int now = p.second;
		if (r_dist[now] < p.first) {
			continue;
		}
		for (auto next_v : rG[now]) {
			if (r_dist[next_v.to] > r_dist[now] + next_v.weight) {
				r_dist[next_v.to] = r_dist[now] + next_v.weight;
				que.push(P(r_dist[next_v.to], next_v.to));
			}
		}
	}

	ll result = 0;
	for (int i = 1; i <= n; ++i) {
		if ((dist[i] == INF) || (r_dist[i] == INF)) {
			continue;
		}
		if (dist[i] + r_dist[i] <= t) {
			result = max(result, (t - dist[i] - r_dist[i]) * a[i]);
		}
	}

	cout << result << endl;

	return 0;
}