| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 938783 | vjudge1 | Toll (BOI17_toll) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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{
}
}