Ping

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
typedef long long ll;
#define F first
#define S second

const int N = 100000;
const ll INF = 1000000000000000005;

int n, m, p;

vector<pair<pair<int, int>, ll>> eg;
vector<pair<int, ll>> g[N+5];
ll dist[N+5];
bool vis[N+5];

ll min_cost() {
	priority_queue<pair<ll, int>> pq;
	pq.push({0, 1});
	dist[1] = 0;

	while (!pq.empty()) {
		int cn = pq.top().S;
		pq.pop();

		if (vis[cn]) continue;
		vis[cn] = true;

		for (auto a : g[cn]) {
			int rn = a.F;
			ll cw = a.S;
			ll nd = dist[cn]+cw;
			if (nd < dist[rn]) {
				dist[rn] = nd;
				pq.push({-nd, rn});
			}
		}
	}

	return dist[n];
}

bool ok(int t) {
	for (int i = 1; i <= N; ++i) {
		g[i].clear();
		dist[i] = INF;
		vis[i] = false;
	}
	for (int i = 0; i < t; ++i) {
		auto ce = eg[i];
		int a = ce.F.F;
		int b = ce.F.S;
		ll w = ce.S;
		g[a].push_back({b, w});
		g[b].push_back({a, w});
	}
	ll cres = min_cost();
	return cres <= p;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m >> p;
	for (int i = 0; i < m; ++i) {
		int a, b;
		ll t;
		cin >> a >> b >> t;
		eg.push_back({{a, b}, t});
	}
	int mt = -1; // edget 0..mt
	for (int jp = (1<<18); jp >= 1; jp /= 2) {
		if (mt+jp <= m && !ok(mt+jp)) mt += jp;
	}
	mt++;
	if (mt > m) {
		cout << "QAQ\n";
		return 0;
	}
	cout << mt << "\n"; // ja aika vika edge+1
	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