Submission

Score: 0

User: C12

Problemset: เดินทางข้ามชุมชน

Language: cpp

Time: 0.003 second

Submitted On: 2026-01-04 22:25:02

#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second
#define pii pair<ll,ll>
#define puii pair<ull,ull>
#define piii pair<ll,pii>
#define ll long long
#define ull unsigned long long
#define mp make_pair
 
#define mpiii(a,b,c) make_pair(a,make_pair(b,c));
// ll mod = 1000000007;

ll n,m,q;
ll a,b,k;
unordered_map<ll,unordered_map<ll,ll>> adj_matrix;
map<ll,vector<ll>> adj_list;

void solving(){

}

void solve(){

    cin >> n >> m >> q;

    for(int i = 0;i < m;i++){
        cin >> a >> b >> k;


        adj_matrix[a][a] = 0;
        adj_matrix[b][b] = 0;

        adj_matrix[a][b] = k;
        adj_matrix[b][a] = k;
        
        if(adj_list.find(b) == adj_list.end()){
            adj_list[b] = vector<ll>();
        }
        if(adj_list.find(a) == adj_list.end()){
            adj_list[a] = vector<ll>();
        }
        adj_list[b].push_back(a);
        adj_list[a].push_back(b);
    }

    queue<pii>que;
    ll t,cost,ncost;

    // cout << '\n';
    for(int i = 0;i < n;i++){
        for(auto x:adj_list[i]){
            que.push(mp(x,adj_matrix[x][i]));\
            // cout << x << ' ' << i << ' ' << adj_matrix[x][i] << ' ' << adj_matrix[x][i] << '\n';
        }
        // cout << '\n';
        while(!que.empty()){
            t = que.front().f;
            cost = que.front().s;
            que.pop();
            for(auto x:adj_list[t]){
                if(x == i) continue;
                ncost = max(cost,adj_matrix[x][t]);
                ncost = max(ncost,adj_matrix[t][x]);
                if(adj_matrix[x].find(i) == adj_matrix[x].end()){
                    adj_matrix[x][i] = LLONG_MAX;
                }
                if(adj_matrix[i].find(x) == adj_matrix[i].end()){
                    adj_matrix[i][x] = LLONG_MAX;
                }
                
                if(ncost < adj_matrix[x][i] || ncost < adj_matrix[i][x]){
                    adj_matrix[x][i] = ncost;
                    adj_matrix[i][x] = ncost;
                    adj_list[x].push_back(i);
                    adj_list[i].push_back(x);
                    que.push(mp(x,ncost));
                }
                // cout << x << ' ' << i << ' ' << ncost << ' ' << adj_matrix[x][i] << '\n';
            }
        }
        // return;
    }

    // cout << '\n';
    // for(int i = 0;i < n;i++){
    //     for(int j = 0;j < n;j++){
    //         if(adj_matrix[i].find(j) != adj_matrix[i].end()){
    //             cout << i << ' ' << j << ' ' << adj_matrix[i][j];
    //         }
    //         else{
    //             cout << i << ' ' << j << ' ' << "NO";
    //         }
    //         cout << '\n';
    //     }
    // }

    // return;

    while(q--){
        cin >> a >> b >> k;

        if(adj_matrix[a].find(b) != adj_matrix[a].end() && k >= adj_matrix[a][b]){
            cout << "YES";
        }
        else{
            cout << "NO";
        }

        cout << '\n';
    }

    return;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    ll q;
 
    // cin >> q;

    // while(q--)
        solve(); 

    return 0;
}
/*
6 8 1 4
4 7 6 2 5 3
1
3
6
1
4
6
5
3


*/