Submission #760386

#TimeUsernameProblemLanguageResultExecution timeMemory
760386shadow_samiToll (BOI17_toll)C++17
8 / 100
3055 ms11708 KiB
#include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef vector<ll> vi; typedef vector<vector<ll>> vvi; typedef pair<ll,ll> pi; #define ff first #define ss second #define fip(a,b) for(ll i = a ; i < b ; i++) #define fjp(a,b) for(ll j = a ; j < b ; j++) #define fp(x,a,b) for(ll x = a ; x < b ; x++) #define fin(a,b) for(ll i = a : i >= b; i--) #define fjn(a,b) for(ll j = a : j >= b; j--) #define fn(x,a,b) for(ll x = a ; x >= b ; x--); #define ordered_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> #define total_one(a) __builtin_popcount(a) #define front_zero(a) __builtin_clzll(a) #define back_zero(a) __builtin_ctzll(a) #define fx(a) for(auto x : a) #define nli "\n" #if ONLINE_JUDGE #define debug(x) cerr<< #x <<" "<< printn(n) << nli; #else #define debug(x) #endif void printn(ll a){ cerr<<a<<" ";} void printn(int a){ cerr<<a<<" ";} template <class T,class V> void _printn(pair<T,V> a){ cerr<<"( "<<a.ff<<" , "<<a.ss<<" ) "<<nli;} template <class T> void _printn(vector<T> a){ cerr<<"[ "; for(auto x : a){ _printn(a); cerr<<nli; } cerr<<"]"<<nli; return; } const ll mx = 1e5+5; ll n,m,k,q,tp,tp2,res,sum,tptp,cnt,ans; bool f = false; vector<pi> ve; vector<pi> adj[mx]; ll dis[mx]; priority_queue<pi,vector<pi>,greater<pi>> pq; void emptify(){ while(pq.size()) pq.pop(); return; } int sr,de; int main(){ ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); // #ifndef ONLINE_JUDGE // freopen("input1.txt","r",stdin); // freopen("output1.txt","w",stdout); // freopen("error1.txt","w",stderr); // #endif cin>>k>>n>>m>>tp2; fip(0,m){ cin>>sr>>de>>tp; ve.push_back({sr,de}); adj[sr].push_back({de,tp}); } while(tp2--){ cin>>sr>>de; fip(0,n+2) dis[i] = 1e18; emptify(); pq.push({0,sr}); while(pq.size()){ auto it = pq.top(); pq.pop(); if(dis[it.ss] < it.ff) continue; dis[it.ss] = it.ff; fx(adj[it.ss]){ if(dis[x.ff] > dis[it.ss] + x.ss) pq.push({dis[it.ss] + x.ss,x.ff}); } } if(dis[de]>1e9) dis[de] = -1; cout<<dis[de]<<nli; } cerr << "time elapsed : " <<setprecision(6)<< clock() * 1000.00 / CLOCKS_PER_SEC << " ms"<<nli; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...