fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define all(v) v.begin(), v.end()
  4. #define rall(v) v.rbegin(), v.rend()
  5. #define ll long long
  6. #define ln '\n'
  7. #define F first
  8. #define S second
  9.  
  10. void solve(){
  11. int n, m, l, u, v, w;
  12. cin >> n >> m >> l;
  13. vector<vector<pair<int, ll>>>adj(n);
  14. for (int i = 0; i < m; ++i) {
  15. cin >> u >> v >> w;
  16. u--, v--;
  17. adj[u].emplace_back(v, w);
  18. adj[v].emplace_back(u, w);
  19. }
  20. auto dijkstra = [&](){
  21. vector<vector<int>>ans(n);
  22. for (int src = 0; src < n; ++src) {
  23. int cnt = 0;
  24. vector<bool>vis(n);
  25. vector<int>dis(n, 1e9);
  26. priority_queue<tuple<int, int, int>>pq;
  27. dis[src] = 0;
  28. pq.push({0, l, src});
  29. while (!pq.empty()){
  30. if(cnt == n){ break; }
  31. int dist, r_l, node;
  32. tie(dist, r_l, node) = pq.top();
  33. dist *= -1;
  34. pq.pop();
  35. if(vis[node]){ continue; }
  36. cnt++;
  37. vis[node] = 1;
  38. for(auto neighbour : adj[node]){
  39. int x = neighbour.F;
  40. ll w = neighbour.S;
  41. if(r_l >= w){
  42. if(dist <= dis[x]){
  43. dis[x] = dist;
  44. pq.push({-dis[x], r_l - w, x});
  45. }
  46. } else {
  47. if(w > l) { continue; }
  48. if(dist + 1 <= dis[x]){
  49. dis[x] = dist + 1;
  50. pq.push({-dis[x], l - w, x});
  51. }
  52. }
  53. }
  54. }
  55. ans[src] = dis;
  56. }
  57. return ans;
  58. };
  59. vector<vector<int>>ans = dijkstra();
  60. int q; cin >> q;
  61. while(q--){
  62. cin >> u >> v;
  63. u--, v--;
  64. if(ans[u][v] == 1e9){
  65. cout << -1 << ln;
  66. continue;
  67. }
  68. cout << ans[u][v] << ln;
  69. }
  70. }
  71.  
  72. int main() {
  73. ios_base::sync_with_stdio(false);
  74. cin.tie(NULL);
  75. cout.tie(NULL);
  76. #ifndef ONLINE_JUDGE
  77. freopen("output.txt", "w", stdout);
  78. #endif
  79. int t_t = 1; //cin >> t_t;
  80. while (t_t--){
  81. solve();
  82. }
  83. return 0;
  84. }
Success #stdin #stdout 0s 5280KB
stdin
3 2 5
1 2 3
2 3 3
2
3 2
1 3
stdout
0
1