| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 132199 | asifthegreat | Jakarta Skyscrapers (APIO15_skyscraper) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
const int N = 30003;
struct node{
int at,cost;
node(int a, int b){
at = a,cost = b;
}
};
bool operator<(node A,node B){
return A.cost > B.cost;
}
vector<pii>edges,graph[N];
int dist[N];
int dijkstra(int s,int dst,int n)
{
priority_queue<node>pq;
for(int i = 0; i < n;i++)dist[i] = 999999999;
dist[s] = 0;
pq.push(node(s,0));
while(!pq.empty()){
node u = pq.top();
//printf("%d\n",u.at);
pq.pop();
if(u.cost != dist[u.at])continue;
for(pii e: graph[u.at]){
//printf("%d: %d -- %d,%d\n",u.at,e.first,dist[e.first],u.cost+e.second);
if(dist[e.first] > u.cost+e.second){
dist[e.first] = u.cost+e.second;
pq.push(node(e.first,dist[e.first]));
}
}
//exit(0);
}
return dist[dst];
}
int main(int argc, char const *argv[])
{
int n,m,b,a;
scanf("%d%d",&n,&m);
int src = -1,destination = -1;
for(int i = 0; i < m;i++){
scanf("%d%d",&a,&b);
if(vis[{a,b}])continue;
vis[{a,b}] = vis[{b,a}] = true;
if(i == 0)src = a;
if(i == 1)destination = a;
int x = 1;
while(a+b*x < n){
graph[a].push_back({a+b*x,x});
x++;
}
x = 1;
while(a-b*x >= 0){
graph[a].push_back({a-b*x,x});
x++;
}
}
//printf("%d %d\n",src,destination);exit(0);
int k = dijkstra(src,destination,n);
if(k == 999999999)printf("-1\n");
else printf("%d\n",k);
return 0;
}