// Online C compiler to run C program online #include int edge[101][101]; int queue[10001][2]; int end = 1; void exchangeQueue(int a, int b) { int k1 = queue[a][0]; int k2 = queue[a][1]; queue[a][0] = queue[b][0]; queue[a][1] = queue[b][1]; queue[b][0] = k1; queue[b][1] = k2; } void insertQueue(int dist, int v) { queue[end][0] = dist; queue[end][1] = v; int curr = end++; while(queue[curr][0] < queue[curr/2][0] && curr >= 2) { exchangeQueue(curr, curr/2); curr /= 2; } } int popQueue() { int node = queue[1][1]; exchangeQueue(1, --end); int curr = 1; while(curr < end) { if (curr*2 > end-1) { //child node X return node; } else if (curr*2 == end-1) { //1 child node if (queue[curr*2][0] < queue[curr][0]) { exchangeQueue(curr, curr*2); curr = curr*2; } else { return node; } } else { //2 child nodes if (queue[curr][0] <= queue[curr*2][0] && queue[curr][0] <= queue[curr*2+1][0]) { //when curr's distance is the smallest return node; } else if (queue[curr*2][0] < queue[curr*2+1][0]) { exchangeQueue(curr*2, curr); curr *= 2; } else { exchangeQueue(curr*2+1, curr); curr = curr*2+1; } } } } int main() { int dist[101]; dist[1] = 0; for (int i = 2; i <= 100; i++) { dist[i] = 1<<30 - 1; } int N, M; scanf("%d %d", &N, &M); for (int i = 1; i <= 100; i++) { for (int j = 1; j <= 100; j++) { edge[i][j] = -1; } } for (int i = 1; i <= 99; i++) { int j = i+1; while (j <= 100 && j <= i + 6) { edge[i][j++] = 1; } } int u, v; for (int i = 1; i <= N; i++) { scanf("%d %d", &u, &v); edge[u][v] = -1; for (int i = 1; i <= 6 && u+i <= 100; i++) { edge[u][u+i] = -1; } for (int i = 1; i <= 6 && u-i >= 1; i++) { edge[u-i][v] = 1; } } for (int i = 1; i <=M; i++) { scanf("%d %d", &u, &v); edge[u][v] = -1; for (int i = 1; i <= 6 && u+i <= 100; i++) { edge[u][u+i] = -1; } for (int i = 1; i <= 6 && u-i >= 1; i++) { edge[u-i][v] = 1; } } for (int i = 1; i <= 100; i++) { insertQueue(dist[i], i); } while (end > 1) { int u = popQueue(); for (int v = 1; v <= 100; v++) { if (edge[u][v] < 0) { continue; } else { if (dist[v] > dist[u] + edge[u][v]) { dist[v] = dist[u] + edge[u][v]; insertQueue(dist[v], v); } } } } printf("%d", dist[100]); return 0; }

제출 #120417

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력: