Ping

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#define INF 1000000001

using namespace std;

typedef pair<int,int> pint;

int main()
{
	cin.tie(0);
	cin.sync_with_stdio(false);
	int pcs, connc, ping;
	cin >> pcs >> connc >> ping;
	queue<pint> q;
	int dists[pcs];
	vector<pint> lines[pcs];
	for (int _ = 1; _ < pcs; _++)
	{
		dists[_] = INF;
	}
	dists[0] = 0;
	for (int i = 0; i < connc; i++)
	{
		int a, b, tp;
		cin >> a >> b >> tp;
		a--; b--;
		q.push(make_pair(b, dists[a] + tp));
		lines[a].push_back(pint(b, tp));
		lines[b].push_back(pint(a, tp));
		while (!q.empty())
		{
			pint curr = q.front();
			q.pop();
			if (curr.second < dists[curr.first])
			{
				dists[curr.first] = curr.second;
				for (pint line : lines[curr.first])
				{
					q.push(make_pair(line.first, curr.second + line.second));
				}
			}
		}
		if (dists[pcs - 1] <= ping)
		{
			cout << (i + 1) << endl;
			return 0;
		}
	}
	cout << "QAQ" << endl;
	return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: WRONG ANSWER

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: WRONG ANSWER

Test 9

Verdict: WRONG ANSWER

Test 10

Verdict: WRONG ANSWER

Test 11

Verdict: ACCEPTED

Test 12

Verdict: WRONG ANSWER

Test 13

Verdict: WRONG ANSWER

Test 14

Verdict: ACCEPTED

Test 15

Verdict: WRONG ANSWER

Test 16

Verdict: ACCEPTED

Test 17

Verdict: TIME LIMIT EXCEEDED