問題設定より、使える辺は \(W_i \ge K\) なる辺だけです。よって、以降はこの条件に違反する辺を取り除いたグラフを考えます。

頂点 \(1\) から頂点 \(N\) まで到達するために通る辺の本数の最小値を求めればこの問題に正解することができ、これは幅優先探索 (BFS) を利用することで実現可能です。

• BFS (幅優先探索) 超入門！ 〜 キューを鮮やかに使いこなす 〜

時間計算量は \(O(N+M)\) 、空間計算量は \(O(N+M)\) です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using Graph=vector<vector<int>>;

const int big=1e9;

int main(){
  int n,m,k;
  cin >> n >> m >> k;
  Graph g(n+1);
  for(int i=0;i<m;i++){
    int u,v,w;
    cin >> u >> v >> w;
    if(w>=k){
      g[u].push_back(v);
      g[v].push_back(u);
    }
  }
  
  vector<int> d(n+1,big);
  queue<int> q;
  d[1]=0;
  q.push(1);

  while(!q.empty()){
    int od=q.front(); q.pop();
    for(auto &nx : g[od]){
      if(d[nx]==big){
        d[nx]=d[od]+1;
        q.push(nx);
      }
    }
  }

  if(d[n]==big){
    cout << "-1\n";
  }
  else{
    cout << d[n] << "\n";
  }
  return 0;
}