#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e18;
const int N=1e5+3;
int n, m, x, h[N];
vector<pair<int,int>> adj[N];
ll dist[N];
signed main(){
cin>>n>>m>>x;
for(int i=1;i<=n;i++)cin>>h[i];
for(int i=1;i<=m;i++){
int u, v, t;
cin>>u>>v>>t;
if(h[u] >= t) adj[u].push_back({v,t});
if(h[v] >= t) adj[v].push_back({u,t});
}
fill(dist,dist+N,INF);
priority_queue<pair<ll,int>> pq;
dist[1] = 0, pq.push({0,1});
while(!pq.empty()) {
auto [d,a] = pq.top(); pq.pop(), d=-d;
if(dist[a] < d) continue;
for(auto [b,w] : adj[a]) {
if(dist[a] < x) {
if(x-dist[a] >= w) {
if(dist[b] > max(dist[a]+w,0LL+x-h[b])) {
dist[b] = max(dist[a]+w,0LL+x-h[b]);
pq.push({-dist[b],b});
}
}else{
if(dist[b] > dist[a]+w+w-(x-dist[a])) {
dist[b] = dist[a]+w+w-(x-dist[a]);
pq.push({-dist[b],b});
}
}
}else if(dist[b] > dist[a]+2*w) {
dist[b] = dist[a]+2*w;
pq.push({-dist[b],b});
}
}
}
if(dist[n] < x)cout<<h[n]-(x-dist[n]) + dist[n]<<'\n';
else if(h[n]+dist[n]>=INF)puts("-1");
else cout<<h[n]+dist[n]<<'\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |