Atcoder ABC 143 Problem E

#include<iostream>
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;

#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);
#define fileio() freopen("input.txt","r",stdin); freopen("output2.txt","w",stdout);
#define ll long long int
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define forn(l,n,i) for(ll i=l;i<n;i++)
#define mp make_pair
#define F first
#define S second

ll inf=1e18;
void get_path(int s,int e,vector<vector<int>>& path,vector<int>& p){
    p.pb(s);
    while(s!=e){
        s=path[s][e];
        p.pb(s);
    }
}

vector<int> travelByCar(ll n,ll l, vector<vector<int>>edges ,vector<vector<int>> queries)
{
    vector<vector<ll>> dist(n+1,vector<ll>(n+1,inf));
    vector<vector<int>> path(n+1,vector<int>(n+1,-1));
    forn(1,n+1,i) {
        dist[i][i]=0;
    }
    for(auto x:edges){
        dist[x[0]][x[1]]=x[2];
        dist[x[1]][x[0]]=x[2];
        path[x[0]][x[1]]=x[1];
        path[x[1]][x[0]]=x[0];
    }
    forn(1,n+1,k){
        forn(1,n+1,i){
            forn(1,n+1,j){
                if(dist[i][k]!=inf && dist[k][j]!=inf && dist[i][j]>dist[i][k]+dist[k][j]){
                    dist[i][j]=dist[i][k]+dist[k][j];
                    path[i][j]=path[i][k];
                }
            }
        }
    }
    vector<int> res(queries.size(),0);
    forn(0,queries.size(),i){
        int a=queries[i][0];
        int b=queries[i][1];
        if(dist[a][b]!=inf){
            vector<int> p;
            get_path(a,b,path,p);
            int ans=0;
            int cur=l;
            forn(0,p.size()-1,j){
                ll val=dist[p[j]][p[j+1]];
                if(val>l){
                    res[i]=-1;
                    break;
                }
                else if(val>cur){
                    cur=l-val;
                    ans++;
                }
                else cur-=val;
            }
            res[i]=ans;
        }
        else res[i]=-1;
    }
    return res;
}

void solve(){
    ll n,m,l;
    cin>>n>>m>>l;
    vector<vector<int>> v(m,vector<int>(3));
    forn(0,m,i) cin>>v[i][0]>>v[i][1]>>v[i][2];
    int q;
    cin>>q;
    vector<vector<int>> que(q,vector<int>(2));
    forn(0,q,i) cin>>que[i][0]>>que[i][1];
    for(int x:travelByCar(n,l,v,que)) cout<<x<<endl;
}

int main(){

    //fastio();
    // fileio();
    ll t;
    // cin>>t;
    t=1;
    while(t--){
        solve();
        // cout<<'\n';
    }
    return 0;
}