Peli

#include<bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define inf ((int)1.01e9)
#define N 2505
typedef long long ll;
typedef pair<int,int> pii;

int n,m,q,z[N][N],oddz[N][N];
vector<int> v[N]; 

// dijkstran
void haku(int S, bool odd) {
    priority_queue<pii> q;
    q.push({0,S});
    while(!q.empty()) {
        auto[e,s] = q.top();
        q.pop();
        e--;
        if (!odd) {
            for (auto i : v[s]) {
                if (z[S][i]<-e) continue;
                z[S][i]=-e;
                q.push({e,i});
            }
        } else {
            for (auto i : v[s]) {
                if (oddz[S][i]<-e 
                && ((oddz[S][i]&1)!=(z[S][i]&1)
                    || (e&1)==(z[S][i]&1)))
                    continue;
                oddz[S][i]=-e;
                q.push({e,i});
            }
        }
    }
}
// perus bfs
void haku2(int S) {
    queue<tuple<int,int,bool>> q;
    q.push({0,S,false});
    while(!q.empty()) {
        auto[e,s,odd] = q.front();
        q.pop();
        e++;
        if (!odd) {
            for (auto i : v[s]) {
                if (z[S][i]<e) {
                    if (oddz[S][i]<e
                    || (e&1)==(z[S][i]&1))
                        continue;
                    oddz[S][i]=e;
                    q.push({e,i,true});
                    continue;
                }
                z[S][i]=e;
                q.push({e,i,false});
            }
        } else {
            for (auto i : v[s]) {
                if (oddz[S][i]<e 
                && ((oddz[S][i]&1)!=(z[S][i]&1)
                    || (e&1)==(z[S][i]&1)))
                    continue;
                oddz[S][i]=e;
                q.push({e,i,true});
            }
        }
    }
}
int main() {
    cin.tie(0)->sync_with_stdio(false);
    cout.tie(0);
    cin>>n>>m>>q; 
    int a,b,x;
    forn(i,m) {
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    forn(i,n) fill(z[i+1],z[i+1]+n+1,inf);
    forn(i,n) fill(oddz[i+1],oddz[i+1]+n+1,inf);
    forn(i,n) z[i+1][i+1]=oddz[i+1][i+1]=0;

    forn(i,n) haku2(i+1);
    // forn(i,n) haku(i+1,true);

    /*
    // debug
    forn(i,n) {
        forn(j,n)
            cout<<z[i+1][j+1]<<' ';
        cout<<endl;
    }
    cout<<endl; 
    forn(i,n) {
        forn(j,n)
            cout<<oddz[i+1][j+1]<<' ';
        cout<<endl;
    }
    cout<<endl;
    //
    */

    forn(i,q) {
        cin>>a>>b>>x;
        if (x>=z[a][b]) 
            if ((x&1)==((z[a][b])&1)||(x>=oddz[a][b]&&(x&1)==((oddz[a][b])&1))) {
                cout<<"YES"<<endl; continue;
            }
        cout<<"NO"<<endl;
    }
}

Test 1

Group: 1, 2

Verdict: ACCEPTED

Test 2

Group: 1, 2

Verdict: ACCEPTED

Test 3

Group: 2

Verdict: ACCEPTED

Test 4

Group: 1, 2

Verdict: ACCEPTED

Test 5

Group: 1, 2

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: ACCEPTED

Test 8

Group: 1, 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 10

Group: 2

Verdict: TIME LIMIT EXCEEDED