// Online C compiler to run C program online #include int edge[101][101]; int Heap[10001][2]; int end = 1; void exchangeHeap(int a, int b) { int k1 = Heap[a][0]; int k2 = Heap[a][1]; Heap[a][0] = Heap[b][0]; Heap[a][1] = Heap[b][1]; Heap[b][0] = k1; Heap[b][1] = k2; } void insertHeap(int dist, int v) { Heap[end][0] = dist; Heap[end][1] = v; int curr = end++; while(Heap[curr][0] < Heap[curr/2][0] && curr >= 2) { exchangeHeap(curr, curr/2); curr /= 2; } } int popHeap() { int node = Heap[1][1]; exchangeHeap(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 (Heap[curr*2][0] < Heap[curr][0]) { exchangeHeap(curr, curr*2); curr = curr*2; } else { return node; } } else { //2 child nodes if (Heap[curr][0] <= Heap[curr*2][0] && Heap[curr][0] <= Heap[curr*2+1][0]) { //when curr's distance is the smallest return node; } else if (Heap[curr*2][0] < Heap[curr*2+1][0]) { exchangeHeap(curr*2, curr); curr *= 2; } else { exchangeHeap(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++) { insertHeap(dist[i], i); } while (end > 1) { int u = popHeap(); 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]; insertHeap(dist[v], v); } } } } printf("%d", dist[100]); return 0; }

제출 #120498

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: