Ping

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

using namespace std;

int main() {
    cin.tie(0);
    cin.sync_with_stdio(false);
    int n, q, p;
    cin>>n>>q>>p;

    int e[n];
    for (int i = 0; i < n; i++) e[i] = INF;
    e[0] = 0;
    int ans = INF;
    vector<pair<int, int>> v[n];
    for (int i = 0; i < q; i++) {
        int a, b, c;
        cin>>a>>b>>c;
        a--; b--;
        if (c <= p && ans == INF) {
            v[a].push_back(make_pair(b, c));
            v[b].push_back(make_pair(a, c));
            stack<int> s;
            s.push(b);
            s.push(a);
            while (s.size() > 0) {
                int w = s.top();

                for (pair<int, int> q : v[w]) {
                    if (e[a] + q.second <= p && e[a] + q.second < e[q.first]) {
                        e[q.first] = e[a]+ q.second;
                        s.push(q.first);
                    }
                }

                s.pop();
            }
            if (e[n - 1] <= p) 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: WRONG ANSWER

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: WRONG ANSWER

Test 15

Verdict: WRONG ANSWER

Test 16

Verdict: WRONG ANSWER

Test 17

Verdict: WRONG ANSWER