Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
signed main(signed argc, char *argv[]) {
int n, m;
cin >> n >> m;
vector<int> a(m), b(m), y(m);
for (int i = 0; i < m; ++i) {
cin >> a[i] >> b[i] >> y[i];
a[i]--;
b[i]--;
}
int q;
cin >> q;
vector<int> v(q), w(q);
for (int i = 0; i < q; ++i) {
cin >> v[i] >> w[i];
v[i]--;
}
if (n > 1000 || m > 2000 || q > 1000) {
return 0;
}
vector<vector<pair<int, int>>> edge(n);
for (int i = 0; i < m; ++i) {
edge[a[i]].push_back(make_pair(b[i], y[i]));
edge[b[i]].push_back(make_pair(a[i], y[i]));
}
for (int i = 0; i < q; ++i) {
int ans = 0;
vector<bool> used(n, false);
queue<int> que;
que.push(v[i]);
while (!que.empty()) {
int node = que.front();
que.pop();
if (!used[node]) {
ans++;
used[node] = true;
for (int j = 0; j < (int) edge[node].size(); ++j) {
if (edge[node][j].second > w[i]) {
que.push(edge[node][j].first);
}
}
}
}
cout << ans << endl;
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment