글 읽기 - 반례 좀 부탁드립니다 + 시도해 본 예시들

paraworld 4년 전 12

말 그대로입니다.시간초과는 어떻게 해결된 듯 한데, 이번엔 제출하자마자 자꾸 틀렸다고 합니다.
문제는, 어디가 문제인지 모르겠습니다...

c#이고, 우선순위 큐는 리스트로 구현했습니다.

코드가 많이 길기는 한데, 봐 주시면 감사하겠습니다.

게시판에 있는 반례들 전부 (케이스 추가해달라는 문서들의 케이스 중 일부가 너무 길어서 그것들은 시도하지 못했습니다) 맞았으며,

유사한 문제로 보이는 111916번을 문제 조건에 맞게 살짝 변경했더니 바로 맞았습니다.

https://www.acmicpc.net/source/18833998

시도해 본 조합들입니다.

3 2

1 3 10

2 1 4

정답

INF

===================

2 1

2 1 1

정답

===================

4 8

1 2 3

2 1 5

4 3 4

2 3 10

1 3 10

2 4 1

3 1 1

1 2 2

정답

===================

2 4

1 2 1

1 2 2

1 2 5

1 2 10

정답

===================

2 3

1 2 1

정답

INF

===================

3 3

2 1 4

정답

INF

===================

5 8

1 2 3

2 1 5

4 3 4

2 3 10

1 3 10

2 4 1

3 1 1

1 2 2

정답

INF

===================

4 6

3 1 2

1 4 2

4 3 2

3 4 2

2 3 2

2 4 2

정답

===================

3 4

1 3 5

2 1 9

2 3 3

2 1 10

정답

===================

12 20

1 2 1

1 3 1

1 4 2

1 5 2

1 6 2

1 7 2

1 8 2

1 9 3

1 10 4

1 11 5

2 11 5

3 11 4

4 11 3

5 11 2

6 11 1

7 10 1

8 10 2

9 10 3

10 11 4

1 11 10

정답

INF

using System;
using System.Collections.Generic;
using System.Text;

// CapitalLetters for class names and methods, camelCase for variable names.
// Write your code clearly enough so that it doesn't need to be commented, or at least, so that it rarely needs to be commented.

namespace Testpad
{
    class BaekJoon1753
    {
        static StringBuilder sb = new StringBuilder();

        // 해당 정점까지의 최단거리, 정점 번호가 0부터 시작함
        static int[] shortcut;

        // 다익스트라에 쓸 우선순위 '큐'
        static List<Dijk> priorList = new List<Dijk>();

        // 인접 리스트
        static List<Path>[] lines;

        // 다익스트라의 우선순위 큐
        struct Dijk
        {
            public int a; // 정점 번호
            public int dist; // 시작점과의 거리

            public Dijk(int a, int dist)
            {
                this.a = a;
                this.dist = dist;
            }
        }

        // 인접 리스트 구현용
        struct Path
        {
            public int b; // 도착지점
            public int w; // 가중치

            public Path(int b, int w)
            {
                this.b = b;
                this.w = w;
            }
        }
        static void Main()
        {
            var inputs = new { temp = Console.ReadLine().Split(" ") };
            int v = int.Parse(inputs.temp[0]); // 정점의 개수 v, 최대 2만
            int e = int.Parse(inputs.temp[1]); // 간선의 개수 e, 최대 30만

            lines = new List<Path>[v]; // 인접 리스트

            for (int i = 0; i < v; i++)
            {
                lines[i] = new List<Path>();
            }

            int k = int.Parse(Console.ReadLine()); // 시작점의 번호 k

            for (int i = 0; i < e; i++)
            {
                inputs = new { temp = Console.ReadLine().Split(" ") };
                // 정점 a에서 정점 b로 가는 가중치 w짜리 간선. 일방통행임
                // 인접행렬은 n²라서 못씀. 인접리스트 써야함
                int a = int.Parse(inputs.temp[0]);
                int b = int.Parse(inputs.temp[1]);
                int w = int.Parse(inputs.temp[2]);

                // 인접 리스트에서 정점 번호가 0부터 시작하니 -1을 해줌
                lines[a - 1].Add(new Path(b - 1, w));
            }

            Dijkstra(v, k);

            // 결과 출력
            foreach (int item in shortcut)
            {
                if (item < int.MaxValue)
                {
                    sb.Append(item);
                    sb.AppendLine();
                }
                else
                {
                    sb.Append("INF");
                    sb.AppendLine();
                }
            }

            Console.Write(sb.ToString());
        }

        static void Dijkstra(int v, int k)
        {
            // 해당 정점까지의 최단거리, 정점 번호가 0부터 시작함
            shortcut = new int[v];

            // 방문한 정점들 목록, 정점 번호가 0부터 시작함
            bool[] used = new bool[v];

            // 방문하지 않은 모든 점은 거리를 '무한대'로 설정
            // 이 문제에서 int.MaxValue면 절대로 나올 수 없는 거리이니 이거면 됨
            for (int i = 0; i < v; i++)
            {
                shortcut[i] = int.MaxValue;
            }

            // 자기 자신과의 거리는 0
            shortcut[k - 1] = 0;

            // 시작점을 리스트에 넣음
            priorList.Add(new Dijk(k - 1, 0));

            while (priorList.Count > 0)
            {
                // 이미 방문 처리된 곳이 아니라면 기준점을 둘러봄
                if (used[priorList[0].a] == false)
                {
                    foreach (var item in lines[priorList[0].a])
                    {
                        // 해당 정점까지의 최단거리를 갱신한 경우, 갱신함
                        if (priorList[0].dist + item.w < shortcut[item.b])
                        {
                            shortcut[item.b] = priorList[0].dist + item.w;
                            priorList.Add(new Dijk(item.b, shortcut[item.b]));
                            PriorerAdd();
                        }
                    }

                    // 전부 확인했으면 기준점을 방문 처리함
                    used[priorList[0].a] = true;
                }

                // 주변을 전부 둘러본 기준점을 리스트에서 제거함
                PriorerRemove();
            }
        }

        // 아래 3개는 우선순위 '큐'를 구현한 거임
        // 이거 안쓰면 n²가 되어서 당연히 시간초과

        // 우선순위 큐에 숫자를 추가하는 연산
        // 이때, 가중치가 가장 작은 경로를 먼저 탐색해야 하니
        // 가장 작은 값을 루트 노드로 보내야 함
        static void PriorerAdd()
        {
            // 추가한 자료의 인덱스 번호
            int current = priorList.Count - 1;

            while (current > 0)
            {
                // 기준점 pivot
                int pivot = current / 2;

                // 추가한 자료의 가중치가 pivot의 것보다 작다면, 계속 진행
                if (priorList[current].dist < priorList[pivot].dist)
                {
                    // 두 자료를 바꿈
                    Swap(current, pivot);
                    current = pivot;
                }
                else
                {
                    break;
                }
            }
        }

        // 우선순위 큐에서 숫자를 빼고, 재정렬하는 연산
        static void PriorerRemove()
        {
            // 맨 가장자리의 두 자료를 바꾸고, 마지막 자료를 제거
            Swap(0, priorList.Count - 1);
            priorList.RemoveAt(priorList.Count - 1);

            // 임시로 올라온 첫 자료를 적절한 위치에 놓음
            int current = 0;

            while (current < priorList.Count - 1)
            {
                // 첫번째 자식 노드의 인덱스 번호
                int pivot = current * 2 + 1;

                // 둘 중 더 작은 쪽과 비교함
                if (pivot < priorList.Count - 1)
                {
                    if (priorList[pivot].dist > priorList[pivot + 1].dist)
                    {
                        pivot++;
                    }
                }

                // 자식 노드의 인덱스 번호
                int child = pivot;

                // 자식 노드가 배열을 벗어나거나 첫 자료의 값이 자식 노드보다 작다면 중단
                if (child > priorList.Count - 1 || priorList[current].dist < priorList[child].dist)
                {
                    break;
                }
                else
                {
                    Swap(current, pivot);
                    current = pivot;
                }
            }
        }

        // 두 자료를 바꾸는 연산
        static void Swap(int current, int pivot)
        {
            var temp = priorList[current];
            priorList[current] = priorList[pivot];
            priorList[pivot] = temp;
        }
    }
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례 좀 부탁드립니다 + 시도해 본 예시들

paraworld 4년 전 12

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말