Submission #3005269

---

Source Code Expand

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <set>
#include <map>
#define REP(i,n) for(ll i = 0; i < (ll)n; i++)
#define INF 1000000000000000
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;

struct edge{ll to, cost;};
typedef pair<ll,ll> P;
struct graph{
  ll V;
  vector<vector<edge> > G;
  vector<ll> d;

  graph(ll n){
    init(n);
  }

  void init(ll n){
    V = n;
    G.resize(V);
    d.resize(V);
    REP(i,V){
      d[i] = INF;
    }
  }

  void add_edge(ll s, ll t, ll cost){
    edge e;
    e.to = t, e.cost = cost;
    G[s].push_back(e);
  }

  void dijkstra(ll s){
    REP(i,V){
      d[i] = INF;
    }
    d[s] = 0;
    priority_queue<P,vector<P>, greater<P> > que;
    que.push(P(0,s));
    while(!que.empty()){
      P p = que.top(); que.pop();
      ll v = p.second;
      if(d[v]<p.first) continue;
      for(auto e : G[v]){
        if(d[e.to]>d[v]+e.cost){
          d[e.to] = d[v]+e.cost;
          que.push(P(d[e.to],e.to));
        }
      }
    }
  }
};

int main(){
  ll n,m,t;
  cin >> n >> m >> t;
  ll a[n];
  graph g1(n); //順方向グラフ
  graph g2(n); //逆方向グラフ
  REP(i,n){
    cin >> a[i];
  }
  REP(i,m){
    ll a,b,c;
    cin >> a >> b >> c;
    g1.add_edge(a-1,b-1,c);
    g2.add_edge(b-1,a-1,c);
  }
  g1.dijkstra(0);
  g2.dijkstra(0);
  ll ans = 0;
  REP(i,n){
    if(t<g1.d[i]+g2.d[i]) continue;
    ll money = a[i]*(t-g1.d[i]-g2.d[i]);
    ans = max(money, ans);
  }
  cout << ans << endl;
  return 0;
}

Submission Info

Judge Result