fork download
copy 
  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
comments (?)
stdin
copy 
3 2 5
1 2 3
2 3 3
2
3 2
1 3
stdout
copy 
0
1
https://ideone.com/mL7ogZ
language:
C++14 (gcc 8.3)
created:
75 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!