Submission #3008310

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template<typename Q_temp>
using smaller_queue = priority_queue <Q_temp, vector<Q_temp>, greater<Q_temp> >;

const int INF = (int) 1e9;
const ll LINF = (ll) 4e18;
const ll MOD = (ll) (1e9 + 7);
const double PI = acos(-1.0);
const int limit = 100010;

#define REP(i,m,n) for(ll i = m; i < (ll)(n); ++i)
#define rep(i,n) REP(i, 0, n)
#define MP make_pair
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << endl
#define NP(v) next_permutation(v.begin(),v.end())
#define debug(x) cout << #x << ":" << x << endl;
#define debug2(x) for(auto a : x) cout << a << " "; cout << endl;
#define debug3(x) rep(i, sizeof(x)) cout << x[i] << " "; cout << endl;

vector<pii> around = {MP(1, 0), MP(-1, 0), MP(0, 1), MP(0, -1)};

//------------------------------------------------------

template <typename T, typename U> class dijkstra {
public:

    struct edge {
        T to;
        U cost;
    };

    using P = pair<U, T>;
    map<T, vector<edge> > E;
    map<T, U> d;

    void calc(T s) {
        priority_queue <P, vector<P>, greater<P> > que;
        rep(i, limit) d[i] = LINF; //INF
        que.emplace(U(0), s);
        d[s] = U(0);
        while (!que.empty()) {
            P p = que.top();
            que.pop();
            T v = p.second;
            if (d[v] < p.first) continue;

            for (auto&& e : E[v]) {
                //if (d.find(e.to) == d.end()) d[e.to] = INF;
                if (d[e.to] > d[v] + e.cost) {
                    d[e.to] = d[v] + e.cost;
                    que.emplace(d[e.to], e.to);
                }
            }
        }
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll n, m, t;
    cin >> n >> m >> t;
    ll money[n];
    rep(i, n) cin >> money[i];
    dijkstra<ll, ll> ds, ds_rev;

    rep(i, m) {
        ll a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        ds.E[a].push_back({b, c});
        ds_rev.E[b].push_back({a, c});
    }

    ds.calc(0);
    ds_rev.calc(0);

    ll ans = 0;

    rep(i, n) {
        if (ds.d[i] + ds_rev.d[i] > t) continue;
        ans = max(ans, money[i] * (t - ds.d[i] - ds_rev.d[i]));
    }
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result