Submission #8058857

---

Source Code Expand

#include <bits/stdc++.h>
 
#define int         long long
#define uint        unsigned int
#define ld          long double
#define showoff     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb          push_back
#define pii         pair<int,int>
#define FOR(i,a,b)  for(int i=a;i<b;++i)
#define RFOR(i,a,b) for(int i=a;i>b;--i)
#define f           first
#define se          second
#define maxn        200005
#define all(v)      v.begin(),v.end()
#define sz(x)       (int)x.size()
#define mod         1000000007
#define pqueue      priority_queue<int>
#define pdqueue     priority_queue< int,vector<int> ,greater< int >>
 
using namespace std;
 
 
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
 
int power(int a,int n)
{
    a %= mod;
    if(n == 1)return a;
    if(n == 0)return 1;
    if(n%2)return (a*(power((a*a)%mod,n/2)%mod))%mod;
    return power((a*a)%mod,n/2)%mod;
}
const int inf = (int) 1e18;
 
int inverse(int x){
    return power(x,mod-2)%mod;//little fermat....
}
vector<pii>adj[305];
int mark[305],n,m,d[305],fl[305],L,ans[305][305];

void dijkstra(int v){

    fill(d,d + 305, inf);
    fill(fl,fl + 305, 0);
    d[v] = 0;
    fl[v] = L;
    priority_queue<pair<pii,int>,vector<pair<pii,int> >, greater<pair<pii,int> > > pq;
    pq.push({{0,-L}, v});
    while(!pq.empty()){
        int u = pq.top().se,cnt = pq.top().f.f,val = -1*pq.top().f.se;
        pq.pop();
      	if(cnt > d[u] || cnt == d[u] && val < fl[u])continue;
        for(auto &p : adj[u]) 
            if(fl[u] >= p.se){
                if(d[p.f] > d[u] || d[p.f] == d[u] && fl[p.f] < fl[u]-p.se){
                    d[p.f] = d[u];
                    fl[p.f] = fl[u]-p.se;
                    pq.push({{d[p.f],-fl[p.f]},p.f});
                } 
            }
            else {
                if(d[p.f] > d[u]+1 || d[p.f] == d[u]+1 && fl[p.f] < L-p.se){
                    d[p.f] = d[u]+1;
                    fl[p.f] = L-p.se;
                    pq.push({{d[p.f],-fl[p.f]},p.f});
                }   
            }
    }
}

signed main()
{
    showoff;
    cin >> n >> m >> L;
    FOR(i,1,m+1){
        int u,v,w;
        cin >> u >> v >> w;
      	if(w > L)continue;
        adj[u].pb({v,w});
        adj[v].pb({u,w});
    }
    FOR(i,1,n+1){
        dijkstra(i);
        FOR(j,1,n+1)ans[i][j] = d[j];
    }
    int q;
    cin >> q;
    while(q--){
        int x,y;
        cin >> x >> y;
        if(ans[x][y] != inf)cout << ans[x][y] << "\n";
        else cout << "-1\n";
    }
    return 0;

}
//*->for large size of matrix take int not long long if possible......
//*->always take maximum as inf for safer side ....s

Submission Info

Judge Result