AtCoder Problems in C++ #F - ヘビの JOI 君 (Snake JOI)

第１６回日本情報オリンピック 予選（過去問）から、その提出コードの解答例です。
AtCoderとは、コンテストを通じて、プログラミングやアルゴリズムを学習するサービスです。
atcoder.jp
プログラミングコンテストとは、「与えられた問題をいかに素早く、正確に」解くことができるかを競うものです。
「競技プログラミング」を略して、「競プロ」などと呼ばれています。

#F - ヘビの JOI 君 (Snake JOI)

atcoder.jp

僕が作成、提出したコードは、以下のとおりです。

/*
AtCoder Problems in C++
#F - ヘビの JOI 君 (Snake JOI)
https://atcoder.jp/contests/joi2017yo/tasks/joi2017yo_f
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(void){
  ll N,M,X;
  cin>>N>>M>>X;
  ll z=10000000000,a,b,d,r,p;
  vector<ll> T(N);
  for(ll i=0;i<N;i++){
    cin>>T[i];
  }
  vector<vector<pair<ll,ll>>> G(N);
  for(ll i=0;i<M;i++){
    cin>>a>>b>>d;
    G[--a].push_back({--b,d});
    G[b].push_back({a,d});
  }
  priority_queue<tuple<ll,ll,ll,ll>> Q;
  vector<vector<vector<ll>>> h(N,vector<vector<ll>>(X+1,vector<ll>(2,z)));
  h[0][X][0]=0;
  Q.push({0,0,0,X});
  while(!(Q.empty())){
    auto[v,d,t,x]=Q.top();
    Q.pop();
    for(auto[u,c] : G[v]){
      r=max(x-c,0LL);
      p=t;
      if(r && (T[u]^(t<<1))==2){
        continue;
      }
      if(T[u]!=1){
        r=X;
        p=T[u]>>1;
      }
      if(h[u][r][p]>h[v][x][t]+c){
        h[u][r][p]=h[v][x][t]+c;
        Q.push({u,-h[u][r][p],p,r});
      }
    }
  }
  for(ll i=0;i<X+1;i++){
    for(ll j=0;j<2;j++){
      z=min(z,h[N-1][i][j]);
    }
  }
  cout<<z<<endl;
  return 0;
}