Cerința

N orașe sunt conectate între ele prin M autostrăzi bidirecționale, fiecare autostradă (a, b) având un cost de tranzit c atașat. Se dorește revizuirea sistemului de taxare, însă sunt câteva aspecte ce trebuie luate în calcul și necesită investigație, deoarece o parte dintre cele N orașe sunt centre comerciale sau turistice importante.

Se dorește să se afle răspunsul la o serie de Q întrebări de forma: (X, T) – câte dintre celelalte N-1 orașe, au acces către orașul X, cu o taxă totală de cel mult T către fiecare oraș?

Date de intrare

Fișierul de intrare tollroads.in conține pe primul rând numerele N, M și Q reprezentând numărul de orașe, numărul de autostrăzi și numărul de interogări. Pe fiecare din următoarele M rânduri sunt scrise câte trei numere a, b, c, separate prin câte un spațiu, reprezentând două orașe între care există o autostradă și costul autostrăzii. Pe următoarele Q rânduri se află scrise câte două numere X și T, separate prin spațiu, reprezentând datele interogărilor, conform enunțului.

Date de ieșire

În fișierul de ieșire tollroads.out se vor scrie pe fiecare dintre primele Q rânduri câte un singur număr, reprezentând răspunsurile la interogări, în ordinea în care ele au fost puse.

Restricții și precizări

• 1 ≤ N ≤ 100.000
• 1 ≤ M ≤ 100.000
• 1 ≤ a, b ≤ N
• 1 ≤ c ≤ 100.000
• 1 ≤ T ≤ 100.000
• 1 ≤ Q ≤ 100
• între orice două orașe poate exista mai mult de o autostrada

Exemplu

tollroads.in

7 8 5
1 2 1
2 3 2
2 4 4
3 5 1
4 5 1
5 6 2
1 6 5
6 7 1
1 6
1 5
1 4
2 3
4 4

tollroads.out

6
5
3
3
5

Explicație

Orașele 2,3,4,5,6,7 au acces către orașul 1 cu taxă maximă 6
Orașele 2,3,4,5,6 au acces către orașul 1 cu taxă maximă 5
Orașele 2,3,5 au acces către orașul 1 cu taxă maximă 4
Orașele 1,3,5 au acces către orașul 2 cu taxă maximă 3
Orașele 2,3,5,6,7 au acces către orașul 4 cu taxă maximă 4

#include <bits/stdc++.h>


using namespace std;

#define inf 0x3f3f3f3f

ifstream cin("tollroads.in");
ofstream cout("tollroads.out");

int n, m, k, X, t, P[100001];
vector<vector<pair<int, int>>> G(100001);

int BFS(int nod){
    queue<int> Q;
    Q.push(nod);
    P[nod] = 0;
    while(!Q.empty()){
        int nod1 = Q.front();
        for(auto x:G[nod1]){
            int y = x.first;
            int c = x.second;
            if(P[y] > P[nod1] + c && P[nod1] + c <= t)
                P[y] = P[nod1] + c, Q.push(y);
        }
        Q.pop();
    }
    int c = 0;
    for(int i = 1; i <= n; ++i){
        if(P[i] <= t)
            c++, P[i] = inf;
    }
    return c-1;
}

int main(){
    cin >> n >> m >> k;
    int a, b, c;
    for(int i = 1; i <= m; ++i)
        cin >> a >> b >> c, G[a].push_back({b, c}), G[b].push_back({a, c});
    for(int i = 1; i <= n; ++i)
        P[i] = inf;
    for(int i = 1; i <= k; ++i){
        cin >> X >> t;
        cout << BFS(X) << '\n';
    }
    return 0;
}