ABC 035 D トレジャーハント

##問題
https://atcoder.jp/contests/abc035/tasks/abc035_d
##見た感じ
町1からほかの町に行くとして、2つ以上の町に滞在する場合を調べる意味はなさそう。
なぜなら、2つ以上の町に滞在したとしたら、滞在した町のうち一番時給のいいとこに時間を全振りすればより儲かるので、求める動き方は一つの町に最短で行ってできるだけ長くそこにいて、最短で帰る動き方の中にある。
だから、各町$i$についてそこにいって帰る最短の時間を$t_i$とすると$(t-t_i )*a_i$がその町を使う調べるべき場合の儲けになって、
これが最大な$i$を調べればいい。
##解法
各町$i$について、その町に行く最短の時間$t1_i$は素直なdijkstraで求めれて、そこから帰る最短の時間$t2_i$は矢印を逆にしたdijkstraで求まる。
最後に$(t-t1_i -t2-_i )*a_i$の最大値を調べればいい。
##ソースコード

const int N_MAX=100005;
int n,m;
ll t,a[N_MAX];
vector<edge> v[N_MAX],vv[N_MAX];

ll  solve(){
    ll d[n+1],dd[n+1];
    priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> que;
    fill(d,d+n+1,INF18);fill(dd,dd+n+1,INF18);
    d[0]=0;dd[0]=0;
    que.push({0,0});
    while(que.size()){
        auto p=que.top();que.pop();
        int w=p.second;
        if(d[w]<p.first)continue;
        for(auto c:v[w]){
            if(minin(d[c.to],d[w]+c.cost)){
                que.push({d[c.to],c.to});
            }
        }
    }
    que.push({0,0});
    while(que.size()){
        auto p=que.top();que.pop();
        int w=p.second;
        if(dd[w]<p.first)continue;
        for(auto c:vv[w]){
            if(minin(dd[c.to],dd[w]+c.cost)){
                que.push({dd[c.to],c.to});
            }
        }
    }
    ll res=0;
    rep(i,n){
        maxin(res,max(0ll,t-d[i]-dd[i])*a[i]);
    }
    return res;
}

int main(){
    int x,y,z;
    //入力
    cin>>n>>m>>t;
    rep(i,n)cin>>a[i];
    rep(i,m){
        cin>>x>>y>>z;
        v[x-1].pb(edge(y-1,z));
        vv[y-1].pb(edge(x-1,z));
    }
    //処理
    auto ans=solve();
    //出力
    cout << ans <<endl;
}