| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 866868 | 1075508020060209tc | Jakarta Skyscrapers (APIO15_skyscraper) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;int m;
int dis[30100];
vector<int>e[30100];
set<int>st[30100];
int vis[30100];
int ar[30100];
int br[30100];
int frm[30100];
signed main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
cin>>n>>m;
for(int i=0;i<m;i++){
cin>>ar[i]>>br[i];
st[ar[i]].insert(br[i]);
// e[ar[i]].push_back(br[i]);
}
for(int i=0;i<n;i++){
for(auto it=st[i].begin();it!=st[i].end();it++){
e[i].push_back(*it);
}
}
for(int i=0;i<n;i++){
dis[i]=2000000000;
}
dis[ar[0]]=0;
for(int ttt=1;ttt<=n;ttt++){
int nw=n;
for(int i=0;i<n;i++){
if(vis[i]){continue;}
if(nw==n||dis[i]<dis[nw]){
nw=i;
}
}
if(nw==n){break;}
if(dis[nw]>1000000000){break;}
vis[nw]=1;
for(int i=0;i<e[nw].size();i++){
if(d==frm[nw]){continue;}
int d=e[nw][i];
int v=nw+d;int t=1;
for(;v<n;){
//int v=nw+t*d;
// dis[v]=min(dis[v],dis[nw]+t);
if(dis[v]>dis[nw]+t){
dis[v]=dis[nw]+t;
frm[v]=d;
}
v+=d;t++;
}
v=nw-d;t=1;
for(;v>=0;){
if(dis[v]>dis[nw]+t){
dis[v]=dis[nw]+t;
frm[v]=d;
}
v-=d;t++;
}
}
}
if(dis[ar[1]]>1000000000){
cout<<-1<<endl;
return 0;
}
cout<<dis[ar[1]]<<endl;
}