This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
#define sqrtn 230
#define maxn 50050
#define mxdist 500000000
vector<int> jump = {0,228,112,74,45,44};
int dist[maxn][231];
int k,no_of_vertex,no_of_edge,no_of_query;
vector<int> top;
vector<int> visited(maxn,0);
vector<vector<pair<int,int> > > adj(maxn);
vector<int> ipos(maxn,0);
void topsort(int node){
visited[node] = 1;
for(auto kk:adj[node]){
if(visited[kk.f]==1){
continue;
}
topsort(kk.f);
}
top.push_back(node);
}
void find(int node){
vector<pair<int,int> > curr;
vector<int> distt(231,INT_MAX);
for(int i=node;i<min(no_of_vertex,node+231);i++){
curr.push_back({ipos[i],i});
}
distt[0] = 0;
sort(curr.begin(),curr.end());
for(int i=0;i<curr.size();i++){
for(auto kk:adj[curr[i].s]){
if(kk.f>node+230){
continue;
}
distt[kk.f-node] = min(distt[kk.f-node],distt[curr[i].s-node]+kk.s);
}
}
for(int i=0;i<231;i++){
dist[node][i] = INT_MAX;
}
for(int i=0;i<curr.size();i++){
dist[node][i] = distt[i];
}
return;
}
int32_t main() {
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin >> k >> no_of_vertex >> no_of_edge >> no_of_query;
int input1,input2,input3;
for(int i=0;i<no_of_edge;i++){
cin >> input1 >> input2 >> input3;
adj[input1].push_back({input2,input3});
}
for(int i=0;i<no_of_vertex;i++){
if(visited[i]==0){
topsort(i);
}
}
reverse(top.begin(),top.end());
for(int i=0;i<top.size();i++){
ipos[top[i]] = i;
}
for(int i=0;i<no_of_vertex;i++){
find(i);
}
for(int i=0;i<no_of_query;i++){
cin >> input1 >> input2;
vector<int> currdist(k,INT_MAX);
if(input1+230>=input2){
if(dist[input1][input2-input1]>=INT_MAX){
cout << -1 << "\n";
}
else{
cout << dist[input1][input2-input1] << "\n";
}
continue;
}
int q = input1/k;
q++;
for(int j=0;j<k;j++){
currdist[j] = dist[input1][q*k+j-input1];
}
while(1){
if(q*k+230>=input2){
int mini = INT_MAX;
for(int j=0;j<k;j++){
mini = min(mini,dist[q*k+j][input2-q*k-j]+currdist[j]);
}
if(mini==INT_MAX){
cout << -1 << "\n";
}
else{
cout << mini << "\n";
}
break;
}
vector<int> next(k,INT_MAX);
for(int j=0;j<k;j++){
/*for(int a=0;a<no_of_vertex;a++){
cout << dist[q*k+j][a] << " ";
}
cout << "\n-----------\n";*/
for(int a=0;a<k;a++){
//cout << dist[q*k+j][k*jump[k]+a] << "---\n";
//cout << j << " " << a << " " << dist[q*k+j][k*jump[k]+a-j] << " " << currdist[j] << " " << k*jump[k]+a << "\n";
next[a] = min(next[a],dist[q*k+j][k*jump[k]+a-j]+currdist[j]);
}
}
/*for(int j=0;j<k;j++){
cout << next[j] << " ";
}
cout << "\n-----\n";*/
/*cout << q*k << "\n";
for(auto kk:next){
cout << kk << " ";
}
cout << endl;*/
currdist = next;
q += jump[k];
}
}
}
Compilation message (stderr)
toll.cpp: In function 'void find(long long int)':
toll.cpp:34:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<curr.size();i++){
~^~~~~~~~~~~~
toll.cpp:45:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<curr.size();i++){
~^~~~~~~~~~~~
toll.cpp: In function 'int32_t main()':
toll.cpp:65:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<top.size();i++){
~^~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |