#include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back const int N=100050; const ll inf=9e18; int h[N],hi[N],n,m,X; ll dist[N][2]; vector<pair<int,int>> E[N]; void Dijkstra() { hi[1]=X; for(int i=2;i<=n;i++) dist[i][0]=dist[i][1]=inf; dist[1][0]=0;dist[1][1]=X; priority_queue<pair<ll,int>> pq; pq.push({0,1}); pq.push({-X,-1}); while(pq.size()) { int u=pq.top().second; ll d=-pq.top().first; pq.pop(); int t=u<0?1:0; u=abs(u); if(dist[u][t]!=d) continue; int H; if(t==1) H=0; else H=hi[u]; for(auto e:E[u]) { int v=e.first; int w=e.second; if(H<=w) { int go=w+w-H; if(dist[v][1]>dist[u][t]+go) { dist[v][1]=dist[u][t]+go; pq.push({-dist[v][1],-v}); } } else { int go=max(w,H-h[v]); if(dist[v][0]>dist[u][t]+go) { dist[v][0]=dist[u][t]+go; hi[v]=H-go; pq.push({-dist[v][0],v}); } } } } } int main() { scanf("%i %i %i",&n,&m,&X); for(int i=1;i<=n;i++) scanf("%i",&h[i]); for(int i=1,u,v,w;i<=m;i++) { scanf("%i %i %i",&u,&v,&w); if(h[u]>=w) E[u].pb({v,w}); if(h[v]>=w) E[v].pb({u,w}); } Dijkstra(); ll ans=min(dist[n][1]+h[n],dist[n][0]+h[n]-hi[n]); printf("%lld\n",ans>=inf?-1:ans); return 0; }

2014_ho_t4.cpp: In function 'int main()':
2014_ho_t4.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i %i",&n,&m,&X);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
2014_ho_t4.cpp:58:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%i",&h[i]);
                        ~~~~~^~~~~~~~~~~~
2014_ho_t4.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i %i",&u,&v,&w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~