Ping

#include <bits/stdc++.h>

#define ll long long
#define ull unsigned long long

#define pii pair<int, int>
#define pll pair<long long, long long>

#define defmod 1000000007
using namespace std;

ll INF = 1LL<<62;
int main(){
  int n, q, p; cin >> n >> q >> p;
  vector<pair<int, pll>> v[101010];
  for(int i = 0; i < q; i++){
    int tu, tv, td; cin >> tu >> tv >> td;
    v[tu].push_back({tv, {td, i+1}});
    v[tv].push_back({tu, {td, i+1}});
  }
  int a = 1, b = q;
  bool paasee = false;
  int lm = -1;
  while(a <= b){
    int m = (a+b)/2;
    priority_queue<pll> q;
    q.push({0, 1});
    vector<ll> dist(101010, INF);
    bool done[101010] = {0};
    //cout << "m on "  << m << " vali: " << a << "-" << b<< endl;
    if(lm == m){
      break;
    }
    while(!q.empty()){
      
	int cur = q.top().second;
	ll dis = -q.top().first;
	q.pop();
	if(done[cur])
	  continue;
	//cout << "nyt: " << cur << " arvolla " << dis << endl;
	done[cur] = true;
	for(auto f: v[cur]){
	   if(f.second.second > m){
	     //cout << cur << "->" << f.first << " ping " << f.second.first << " ei hyvaksytty " << endl;
	      continue;
	   }
	   if(dis+f.second.first < dist[f.first]){
	     dist[f.first] = dis+f.second.first;
	     q.push({-dist[f.first], f.first});
	   }
	     
	}
    }
    if(dist[n] <= p){
      b = m;
      paasee = true;
    }
    else{
      a = m+1;
    }
    lm = m;
  }
  if(!paasee){
      cout << "QAQ" << endl;
  }
  else{
    cout << (a+b)/2 << endl;
  }
  
  return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED