Submission #2560043

---

Source Code Expand

#include <bits/stdc++.h>
#define int long long
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef pair<int,int>P;
vector<P>v[100009],rv[100009];
int n,m,t;
int d[100009],rd[100009],wei[100009];
void dij1(){
  r(i,100009)d[i]=1e13;
  priority_queue<P,vector<P>,greater<P> >q;
  q.push(P(0,0));
  d[0]=0;
  while(!q.empty()){
    P p=q.top();q.pop();
    int now=p.second;
    int co=p.first;
    if(d[now]<co)continue;
    r(i,v[now].size()){
      int nex=v[now][i].first;
      int cost=v[now][i].second+co;
      if(d[nex]<=cost)continue;
      d[nex]=cost;
      q.push(P(cost,nex));
    }
  }
}
void dij2(){
  r(i,100009)rd[i]=1e13;
  priority_queue<P,vector<P>,greater<P> >q;
  q.push(P(0,0));
  rd[0]=0;
  while(!q.empty()){
    P p=q.top();q.pop();
    int now=p.second;
    int co=p.first;
    if(rd[now]<co)continue;
    r(i,rv[now].size()){
      int nex=rv[now][i].first;
      int cost=rv[now][i].second+co;
      if(rd[nex]<=cost)continue;
      rd[nex]=cost;
      q.push(P(cost,nex));
    }
  }
}
int ans=0;
main(){
  cin>>n>>m>>t;
  r(i,n)cin>>wei[i];
  r(i,m){
    int a,b,c;
    cin>>a>>b>>c;a--;b--;
    v[a].push_back(P(b,c));
    rv[b].push_back(P(a,c));
  }
  dij1();
  dij2();
  r(i,n){
    if(d[i]==1e13||rd[i]==1e13)continue;
    int x=t-d[i]-rd[i];
    ans=max(ans,x*wei[i]);
  }
  cout<<ans<<endl;
}

Submission Info

Judge Result