제출 #18888

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
18888		chan492811	Jakarta Skyscrapers (APIO15_skyscraper)	C++98	57 / 100	408 ms	17108 KiB

skyscraper

#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

struct data{
    int to,dist;
};
struct cmp{
    bool operator()(data d1,data d2){
        return d1.dist>d2.dist;
    }
};
int n,m;
int dist[2010];
int graph[2010][2010];
data arr[30010];
bool visit[2010];

void dij(int a){
    int i,j,flag=1,now;
    data s;
    while(flag){
        flag=0; now=21e8;
        for(i=0;i<n;i++){
            if(!visit[i] && dist[i] && dist[i]<now) a=i,flag=1,now=dist[i];
        }
        if(!flag) break; visit[a]=1;
        for(i=0;i<n;i++){
            if(!graph[a][i]) continue;
            if(!dist[i] || dist[i]>dist[a]+graph[a][i]) dist[i]=dist[a]+graph[a][i];
        }
    }
}
int main(){
    int i,j;
    scanf("%d %d",&n,&m);
    for(i=0;i<m;i++) scanf("%d %d",&arr[i].to,&arr[i].dist),visit[arr[i].to]=1;
    for(i=0;i<m;i++){
        for(j=0;j<n;j++){
            if(!(abs(arr[i].to-j)%arr[i].dist)){
                if(!graph[arr[i].to][j]) graph[arr[i].to][j]=abs(arr[i].to-j)/arr[i].dist;
                else graph[arr[i].to][j]=min(graph[arr[i].to][j],abs(arr[i].to-j)/arr[i].dist);
            }
        }
    }
    memset(visit,0,sizeof(visit));
    dist[arr[0].to]=1;
    dij(0);
    if(!visit[arr[1].to]) printf("-1");
    else printf("%d",dist[arr[1].to]-1);
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 0 / 43