Submission #8048273


Source Code Expand

Copy
#include <bits/stdc++.h>

#define ll long long int
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define sep(i,a,b) for(ll i=a-1;i>=b;i--)
#define vi vector<ll>
#define pii pair<int,int>
#define vii vector< pair<int,int> >
#define pb push_back
#define inf 1000000000000
#define hell 1000000007

using namespace std;

ll n,m,l;
vector < pii > adj[500];
vector <vi> a(501,vi(501,inf));
struct comp{
    bool operator()(const pii &a,const pii &b){
        return a.second>b.second;
    }
};

ll helper(ll s,ll t){
    priority_queue <pii, vector <pii> , comp> pq;
    vi par(n+1,-1);
    vi dist(n+1,inf);
    dist[s]=0;
    pq.push({s,0});
    while(!pq.empty()){
        pii p=pq.top();
        pq.pop();
        for(pii &x:adj[p.first]){
            ll u=p.first;
            ll v=x.first;
            ll w=x.second;
            if(dist[v]>dist[u]+w){
                par[v]=u;
                dist[v]=dist[u]+w;
                pq.push({v,dist[v]});
            }
        }
    }
    if(par[t]==-1)
        return -1;
    ll ans=0;
    vi v;
    while(t!=s&&par[t]!=-1){
        v.pb(t);
        t=par[t];
    }
    v.pb(s);
    ll csum=l;
    //cout<<"path"<<" ";
    reverse(begin(v),end(v));/*
    for(ll x:v)
        cout<<x<<" ";
    cout<<"\n";*/
    rep(i,1,v.size()){
        if(csum-a[v[i-1]][v[i]]<0){
            csum=l-a[v[i-1]][v[i]];
            ans++;
        }
        else
            csum-=a[v[i-1]][v[i]];
    }
    return ans;
}

void solve()
{
    cin>>n>>m>>l;
    rep(i,0,m){
        ll u,v,c;
        cin>>u>>v>>c;
        if(c>l)
            continue;
        adj[u].pb({v,c});
        adj[v].pb({u,c});
        a[u][v]=min(a[u][v],c);
        a[v][u]=min(a[v][u],c);
    }
    ll q;
    cin>>q;
    while(q--){
        ll s,t;
        cin>>s>>t;
        cout<<helper(s,t)<<"\n";
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll t;
    t=1;
    //cin>>t;
    while(t--){
        solve();
    }
}

Submission Info

Submission Time
Task E - Travel by Car
User rocket_racoon
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2075 Byte
Status
Exec Time 2103 ms
Memory 3584 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 00-sample-00, 00-sample-01, 00-sample-02
All 0 / 500 00-sample-00, 00-sample-01, 00-sample-02, 01-handmade-03, 01-handmade-04, 01-handmade-05, 01-handmade-06, 01-handmade-07, 02-random-08, 02-random-09, 02-random-10, 02-random-11, 02-random-12, 02-random-13, 02-random-14, 02-random-15, 02-random-16, 02-random-17, 02-random-18, 02-random-19, 02-random-20, 02-random-21, 02-random-22, 02-random-23, 02-random-24, 02-random-25, 02-random-26, 02-random-27, 02-random-28, 02-random-29, 02-random-30, 02-random-31, 02-random-32, 02-random-33, 02-random-34, 02-random-35, 02-random-36, 02-random-37, 02-random-38, 02-random-39, 02-random-40, 02-random-41, 02-random-42, 02-random-43, 02-random-44, 02-random-45, 02-random-46, 02-random-47, 02-random-48, 02-random-49
Case Name Status Exec Time Memory
00-sample-00 2 ms 2304 KB
00-sample-01 2 ms 2304 KB
00-sample-02 2 ms 2304 KB
01-handmade-03 71 ms 2560 KB
01-handmade-04 2103 ms 3584 KB
01-handmade-05 2103 ms 2432 KB
01-handmade-06 661 ms 2560 KB
01-handmade-07 658 ms 2560 KB
02-random-08 7 ms 2304 KB
02-random-09 139 ms 2304 KB
02-random-10 1495 ms 2432 KB
02-random-11 40 ms 2304 KB
02-random-12 115 ms 2304 KB
02-random-13 356 ms 2304 KB
02-random-14 2103 ms 2816 KB
02-random-15 107 ms 2560 KB
02-random-16 712 ms 2304 KB
02-random-17 775 ms 2432 KB
02-random-18 89 ms 2304 KB
02-random-19 3 ms 2304 KB
02-random-20 1312 ms 2560 KB
02-random-21 344 ms 2304 KB
02-random-22 2 ms 2304 KB
02-random-23 1233 ms 2560 KB
02-random-24 2103 ms 2944 KB
02-random-25 1460 ms 2560 KB
02-random-26 4 ms 2304 KB
02-random-27 31 ms 2432 KB
02-random-28 2103 ms 2688 KB
02-random-29 1645 ms 2688 KB
02-random-30 143 ms 2560 KB
02-random-31 37 ms 2304 KB
02-random-32 610 ms 2304 KB
02-random-33 2103 ms 2432 KB
02-random-34 2103 ms 2688 KB
02-random-35 1309 ms 2560 KB
02-random-36 97 ms 2304 KB
02-random-37 778 ms 2304 KB
02-random-38 2 ms 2304 KB
02-random-39 13 ms 2304 KB
02-random-40 1402 ms 2560 KB
02-random-41 2026 ms 2432 KB
02-random-42 13 ms 2304 KB
02-random-43 2103 ms 2944 KB
02-random-44 3 ms 2304 KB
02-random-45 118 ms 2560 KB
02-random-46 61 ms 2304 KB
02-random-47 2103 ms 2432 KB
02-random-48 2 ms 2304 KB
02-random-49 362 ms 2432 KB