Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #ifdef _DEBUG
- #define _GLIBCXX_DEBUG
- #endif
- #define _CRT_SECURE_NO_WARNINGS
- #include <ext/pb_ds/assoc_container.hpp>
- #include <bits/stdc++.h>
- using namespace __gnu_pbds;
- using namespace std;
- typedef long long ll;
- typedef vector<ll> vll;
- typedef pair<int, int> pii;
- typedef vector<int> vi;
- typedef long double ld;
- typedef tree<pair<ll, int>, null_type, less<pair<ll, int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
- #define mk make_pair
- #define inb push_back
- #define enb emplace_back
- #define X first
- #define Y second
- #define all(v) v.begin(), v.end()
- #define sqr(x) (x) * (x)
- #define TIME 1.0 * clock() / CLOCKS_PER_SEC
- #define y1 AYDARBOG
- //continue break pop_back return
- int solve();
- int main()
- {
- //ios_base::sync_with_stdio(0);
- //cin.tie(0);
- #define TASK "treedp"
- #ifndef _DEBUG
- //freopen(TASK".in", "r", stdin), freopen(TASK".out", "w", stdout);
- #endif
- solve();
- #ifdef _DEBUG
- fprintf(stderr, "\nTIME: %.3f\n", TIME);
- #endif
- }
- const int INF = 2e9 + 7;
- const ll LINF = 1e18;
- const int BUFSZ = (int)1e6 + 7;
- char buf[BUFSZ];
- string get_str()
- {
- scanf(" %s", buf);
- return string(buf);
- }
- struct edge
- {
- int a, b, cst;
- edge() {};
- edge(int a, int b, int cst) : a(a), b(b), cst(cst) {};
- bool operator< (edge x) const
- {
- if (cst == x.cst)
- {
- if (a == x.a)
- {
- return b < x.b;
- }
- return a < x.a;
- }
- return cst < x.cst;
- }
- void print()
- {
- printf("FROM: %d TO: %d T: %d\n", a + 1, b + 1, cst);
- }
- };
- int solve()
- {
- int n, m, d;
- scanf("%d %d %d", &n, &m, &d);
- vector<set<edge>> G(n);
- for (int i = 0; i < m; ++i)
- {
- edge e;
- scanf("%d %d %d", &e.a, &e.b, &e.cst);
- --e.a, --e.b;
- G[e.a].insert(e);
- swap(e.a, e.b);
- G[e.a].insert(e);
- }
- int q;
- scanf("%d", &q);
- while (q--)
- {
- int s, f;
- scanf("%d %d", &s, &f);
- --s, --f;
- if (s == f)
- {
- puts("0");
- continue;
- }
- int ans = INF;
- queue<edge> q;
- queue<int> dd;
- vector<set<edge>> g = G;
- for (auto x : g[s])
- {
- q.push(x);
- dd.push(1);
- }
- g[s].clear();
- while (!q.empty())
- {
- edge cur = q.front();
- int cdst = dd.front();
- dd.pop();
- //printf("CURDST: %d CUR: ", cdst);
- //cur.print();
- q.pop();
- int u = cur.b;
- if (u == f)
- {
- ans = cdst;
- break;
- }
- int t = cur.cst;
- for (auto &x : g[u])
- {
- if (abs(x.cst - t) > d)
- continue;
- //x.print();
- if (m > 1000 && x.b == f)
- {
- ans = cdst + 1;
- break;
- }
- q.push(x);
- dd.push(cdst + 1);
- }
- if (ans != INF)
- {
- break;
- }
- for (auto it = g[u].begin(); it != g[u].end();)
- {
- if (abs((*it).cst - t) > d)
- {
- ++it;
- }
- else
- {
- auto it1 = it;
- ++it;
- g[u].erase(*it1);
- }
- }
- }
- if (ans == INF)
- puts("-1");
- else
- printf("%d\n", ans);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement