Peli

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;


int main(){
    cin.tie(0)->sync_with_stdio(NULL);
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<int>> v(n+1);
    for(int i = 0; i < m; i++){
        int a, b; cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    vector<vector<vector<int>>> memo(n+1);
    for(int iii = 0; iii < q; iii++){
        int a, b; ll x;
        cin >> a >> b >> x;

        if(memo[a].size() == 0){
            vector<vector<int>> res(n+1, vector<int>(2, -1));
            priority_queue<tuple<int, int, int>> q; // -distance, vertex, parity
            q.push(make_tuple(0, a, 0));
            while(q.size() > 0){
                tuple<int, int, int> t = q.top(); q.pop();
                int d = get<0>(t);
                int i = get<1>(t);
                int p = get<2>(t);
                if(res[i][p] != -1) continue;
                res[i][p] = -d;
                for(int j : v[i]){
                    if(res[j][1-p] != -1) continue;
                    q.push(make_tuple(d-1, j, 1-p));
                }
            }
            memo[a] = res;
        }

        if(x % 2 == 0){
            if(memo[a][b][0] != -1 && memo[a][b][0] <= x) cout << "YES\n";
            else cout << "NO\n";
        }
        if(x % 2 == 1){
            if(memo[a][b][1] != -1 && memo[a][b][1] <= x) cout << "YES\n";
            else cout << "NO\n";
        }
    }

}

Test 1

Group: 1, 2

Verdict: ACCEPTED

Test 2

Group: 1, 2

Verdict: ACCEPTED

Test 3

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 4

Group: 1, 2

Verdict: ACCEPTED

Test 5

Group: 1, 2

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 7

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 1, 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 10

Group: 2

Verdict: TIME LIMIT EXCEEDED