Ping

#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#define N 2048
#define INF 1000000001

using namespace std;

/*
pcs = koneita
connc = yhteyksiä max
ping = max haluttu ping
dists = etäisyydet[kone]
conn = yhteydet[kone][i]
start = yhteyden alku
end = yhteyden loppu
this_ping = yhteyden ping
pcstack = dijkstran hakupino
curr = alkio sen päällä
con = läpikäytävä alkio
*/

int main() {
	cin.tie(0);
	cin.sync_with_stdio(false);
	int pcs, connc, ping;
	cin>>pcs>>connc>>ping;

	int dists[pcs];
	for (int i = 0; i < pcs; i++) dists[i] = INF;
	dists[0] = 0;
	int ans = INF;
	vector<pair<int, int>> conn[pcs];
	for (int i = 0; i < connc; i++) {
		int start, end, this_ping;
		cin>>start>>end>>this_ping;
		start--; end--;
		if (this_ping <= ping && ans == INF) {
			conn[start].push_back(make_pair(end, this_ping));
			conn[end].push_back(make_pair(start, this_ping));
			stack<int> pcstack;
			pcstack.push(start);
			while (pcstack.size() > 0) {
				int curr = pcstack.top();
				pcstack.pop();
				for (pair<int, int> con : conn[curr]) {
					if (dists[curr] + con.second <= ping
							&& dists[curr] + con.second < dists[con.first]) {
						dists[con.first] = dists[curr]+ con.second;
						pcstack.push(con.first);
					}
				}
			}
			if (dists[pcs - 1] <= ping) ans = i;
		}
	}

	if (ans == INF) cout<<"QAQ"<<endl;
	else cout<<ans + 1<<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: TIME LIMIT EXCEEDED

Test 17

Verdict: ACCEPTED