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, ei tarvita
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)) 
                    continue;
                oddz[S][i]=-e;
                q.push({e,i});
            }
        }
    }
}

void haku2(int S, bool odd) {
    queue<pii> q;
    q.push({0,S});
    while(!q.empty()) {
        auto[e,s] = q.front();
        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)) 
                    continue;
                oddz[S][i]=e;
                q.push({e,i});
            }
        }
    }
}
int main() {
    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]=0;

    forn(i,n) haku2(i+1,false);
    forn(i,n) haku2(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: TIME LIMIT EXCEEDED

Test 2

Group: 1, 2

Verdict: TIME LIMIT EXCEEDED

Test 3

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 4

Group: 1, 2

Verdict: TIME LIMIT EXCEEDED

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