Submission #1109633

#TimeUsernameProblemLanguageResultExecution timeMemory
1109633theSkeletonToll (BOI17_toll)C++17
8 / 100
3051 ms94280 KiB
//!!in the name of god!! #include<bits/stdc++.h> #define space <<' '<< #define endl '\n' #define inf 1e9 #define F first #define S second #define PB push_back #define PF push_front #define pll pair<ll,ll> #define pii pair<int,int> #define md(a) ((a+mod)%mod) #define MP(a,b) make_pair(a,b) #define all(a) a.begin(),a.end() #define MT(a,b,c) make_tuple(a,b,c) #define has(a,b) (a.find(b)!=a.end()) typedef long long ll; using namespace std; template<typename t> using heap= priority_queue<t,vector<t>,greater<t>>; const int mx = 5e4+5; const int lg = 32; map<int,ll> adj[mx][lg]; int glg(int v){ if(v<2)return 0; return glg(v/2)+1; } int main(){ std::ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); int k,n,m,o; cin>>k>>n>>m>>o; for(int u,v,t;m--;) cin>>u>>v>>t, adj[u][0][v]=t; for(int t=0;t<n;t++) for(int p=1;p<lg;p++){ for(auto e:adj[t][p-1]) for(auto d:adj[e.F][p-1]) if(has(adj[t][p],d.F)) adj[t][p][d.F]=min(adj[t][p][d.F],e.S+d.S); else adj[t][p][d.F]=e.S+d.S; } map<int,ll> cn,te; for(int a,b;o--;){ cin>>a>>b; int c=a/k,t=b/k; cn.clear(); cn[a]=0; while(c<t){ te.clear(); int ne=glg(c-t); for(auto e:cn) for(auto d:adj[e.F][ne]) if(has(te,d.F)) te[d.F]=min(te[d.F],e.S+d.S); else te[d.F]=e.S+d.S; cn=te; c+=1<<ne; } if(has(cn,b)) cout<<cn[b]<<endl; else cout<<-1<<endl; } 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...