| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 938783 | vjudge1 | Toll (BOI17_toll) | C++17 | 0 ms | 0 KiB |
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>
#define int long long
#define endl "\n"
using namespace std;
signed main(){
int k,n,m,o;
cin>>k>>n>>m>>o;
if(k==1){
vector<int>tree;
for(int i=0;i<n;i++)tree.push_back(-1);
for(int i=0;i<m;i++){
int a,b,t;
cin>>a>>b>>t;
tree[a]=t;
}
for(int i=0;i<o;i++){
int a,b;
cin>>a>>b;
int sum=0;
bool flag=false;
for(int j=a;j<b;j++){
if(tree[j]==-1){
flag=true;
}else{
sum+=tree[j];
}
}
if(flag==true){
cout<<-1<<endl;
}else{
cout<<sum<<endl;
}
}
}else if (o<=3000){
vector<vector<int>>tree;
tree.resize(n);
for(int i=0;i<n;i++){
for(int j=0;j<k;j++)tree[i].push_back(-1);
}
for(int i=0;i<m;i++){
int a,b.t;
cin>>a>>b>>t;
int b1=b%k;
tree[a][b1]=t;
}
for(int i=0;i<o;i++){
int a,b;
cin>>a>>b;
int a1=a/k;
int b1=b/k;
int B=b%k;
vector<int>shortest=tree[a];
int ans;
for(int j=a1+1;j<b1+1;j++){
vector<int>novi(k,INT_MAX);
for(int r=0;r<k;r++){
for(int l=0;l<k;l++){
int current=j*k+r;
if(current==b)ans=shortest[r];
if(shortest[r]!=-1&&tree[current][l]!=-1){
novi[l]=min(novi[l],shortest[r]+tree[current][l]);
}
}
}
for(int r=0;r<k;r++){
if(novi[r]==INT_MAX){
shortest[r]=-1;
}else shortest[r]=novi[r];
}
}
cout<<ans<<endl;
}
}else{
}
}