모든 컴퓨터 사이언티스트는 다익스트라 알고리즘(https://en.wikipedia.org/wiki/...)에 대해 잘 알 것입니다. 이것은, 주어진 그래프에 대해 단일 출발지 최단 경로를 구하는 알고리즘입니다. 이 알고리즘을 실행할 때, 우리는 액티브 정점들의 집합을 유지합니다. 각 반복마다 최단 현재 거리를 지닌 액티브 정점을 선택한 뒤 작업합니다. 정점에 대해 작업할 때, 밖으로 향하는 간선들을 검사합니다. 그 간선들 중 하나를 이용하여 어떤 인접 정점을 향한 거리를 개선할 수 있을 때마다, 그렇게 한 뒤 그 인접 정점을 액티브로 표시합니다.
모든 간선의 길이가 음수가 아닐 때 그 알고리즘은 효율적인 걸로 잘 알려져있습니다. 이 문제에서 제공하는 레퍼런스 구현은 그러한 그래프에 대해 O(mlogn) 시간에 작동합니다.(이때 m은 간선의 수, n은 정점의 수)
간선에 음의 길이를 허용한다면 문제가 지저분해지기 시작합니다. 최단 단순 경로(반복되지 않은 정점들의 경로)를 그러한 그래프 속에서 찾는 것은 사실 NP-hard 문제입니다. 다익스트라 알고리즘의 일부 버전은 그러한 그래프에 대해서 빨리 완수되지만 종종 부정확한 결과를 내놓습니다. 우리의 레퍼런스 구현은 그런 경우는 아닙니다. 우리의 레퍼런스 구현은 사실 약간 다른 문제를 풉니다. 이것은, 각 정점 v마다, 시작 정점에서 v로 가는 최단 walk의 길이를 구합니다. (walk란 반복된 정점과 간선을 포함할 수도 있는 경로path입니다. 모든 간선의 길이가 양수라면 최단 walk는 최단 경로일 수밖에 없음을 유의하세요.)
종종 시작 정점으로부터 어떤 정점 v로 향하는 최단 walk가 없을 수도 있습니다. 왜냐하면 모든 walk에서 더 짧은 방법을 찾을 수 있기 때문입니다. 그러한 입력에서 우리의 레퍼런스 구현은 절대 종료되지 않습니다.
이 문제에서, 단어 'graph'는 언제나 중복된 간선이나 self-loop가 없는 direct weighted 그래프를 의미합니다. 글자 n과 m은 이것의 정점의 수와 간선의 수를 의미합니다. 정점은 0부터 n-1로 숫자지어집니다. 시작 정점은 0입니다.
우리는 당신이 다익스트라 알고리즘이 종료가 되지만, 이것의 시간 복잡도가 정점의 수에 대해 지수적인 시간 복잡도를 갖는 그래프가 존재한다는 것을 보여주기를 바랍니다.
레퍼런스 구현은 PROCESSED_VERTICES라는 변수를 지닙니다. 당신은 p라는 여러 값들이 주어집니다. 각 p에 대해, 우리의 구현이 유한적으로 많은 단계 내에 종료가 되고, 마지막에 PROCESSED_VERTICES라는 값이 정확히 p인 어떠한 유요한 그래프를 만드시오.
입력
당신은 파일 d2.in이 주어집니다. 파일의 첫 줄에는 테스트 케이스의 수를 의미하는 정수 t가 적혀있습니다. 각 테스트 케이스의 앞에는 공백 줄이 하나 주어집니다. 각 테스트케이스는 숫자 p가 적힌 한 줄로 구성됩니다. 당신은 1 <= p <= 10,000,000을 가정하여도 좋습니다.
출력
유요한 그래프에서는, 1 <= n <= 60이고 각 간선의 길이는 사인드 32 비트 정수의 변수 내에 들어맞습니다.
각 그래프는 일련의 m+2 줄로 출력되어야 합니다. 이러한 줄들의 첫 줄은 n을 포함하여야 하고 두 번째 줄은 m을 포함하여야 하고, 그 다음 각 m 줄은 간선(0과 n-1로 이루어진 양 끝 점의 정점의 번호)과 그 다음으로 길이를 의미하는 세 정수를 포함하여야 합니다.
힌트
이 그래프에서, 우리의 구현은 정확히 6개의 정점을 처리합니다. 0, 33, 11, 7, 11(다시), 1.
leeingyun96 2년 전
문제
모든 컴퓨터 사이언티스트는 다익스트라 알고리즘(https://en.wikipedia.org/wiki/...)에 대해 잘 알 것입니다. 이것은, 주어진 그래프에 대해 단일 출발지 최단 경로를 구하는 알고리즘입니다. 이 알고리즘을 실행할 때, 우리는 액티브 정점들의 집합을 유지합니다. 각 반복마다 최단 현재 거리를 지닌 액티브 정점을 선택한 뒤 작업합니다. 정점에 대해 작업할 때, 밖으로 향하는 간선들을 검사합니다. 그 간선들 중 하나를 이용하여 어떤 인접 정점을 향한 거리를 개선할 수 있을 때마다, 그렇게 한 뒤 그 인접 정점을 액티브로 표시합니다.
모든 간선의 길이가 음수가 아닐 때 그 알고리즘은 효율적인 걸로 잘 알려져있습니다. 이 문제에서 제공하는 레퍼런스 구현은 그러한 그래프에 대해 O(mlogn) 시간에 작동합니다.(이때 m은 간선의 수, n은 정점의 수)
간선에 음의 길이를 허용한다면 문제가 지저분해지기 시작합니다. 최단 단순 경로(반복되지 않은 정점들의 경로)를 그러한 그래프 속에서 찾는 것은 사실 NP-hard 문제입니다. 다익스트라 알고리즘의 일부 버전은 그러한 그래프에 대해서 빨리 완수되지만 종종 부정확한 결과를 내놓습니다. 우리의 레퍼런스 구현은 그런 경우는 아닙니다. 우리의 레퍼런스 구현은 사실 약간 다른 문제를 풉니다. 이것은, 각 정점 v마다, 시작 정점에서 v로 가는 최단 walk의 길이를 구합니다. (walk란 반복된 정점과 간선을 포함할 수도 있는 경로path입니다. 모든 간선의 길이가 양수라면 최단 walk는 최단 경로일 수밖에 없음을 유의하세요.)
종종 시작 정점으로부터 어떤 정점 v로 향하는 최단 walk가 없을 수도 있습니다. 왜냐하면 모든 walk에서 더 짧은 방법을 찾을 수 있기 때문입니다. 그러한 입력에서 우리의 레퍼런스 구현은 절대 종료되지 않습니다.
이 문제에서, 단어 'graph'는 언제나 중복된 간선이나 self-loop가 없는 direct weighted 그래프를 의미합니다. 글자 n과 m은 이것의 정점의 수와 간선의 수를 의미합니다. 정점은 0부터 n-1로 숫자지어집니다. 시작 정점은 0입니다.
우리는 당신이 다익스트라 알고리즘이 종료가 되지만, 이것의 시간 복잡도가 정점의 수에 대해 지수적인 시간 복잡도를 갖는 그래프가 존재한다는 것을 보여주기를 바랍니다.
레퍼런스 구현은 PROCESSED_VERTICES라는 변수를 지닙니다. 당신은 p라는 여러 값들이 주어집니다. 각 p에 대해, 우리의 구현이 유한적으로 많은 단계 내에 종료가 되고, 마지막에 PROCESSED_VERTICES라는 값이 정확히 p인 어떠한 유요한 그래프를 만드시오.
입력
당신은 파일 d2.in이 주어집니다. 파일의 첫 줄에는 테스트 케이스의 수를 의미하는 정수 t가 적혀있습니다. 각 테스트 케이스의 앞에는 공백 줄이 하나 주어집니다. 각 테스트케이스는 숫자 p가 적힌 한 줄로 구성됩니다. 당신은 1 <= p <= 10,000,000을 가정하여도 좋습니다.
출력
유요한 그래프에서는, 1 <= n <= 60이고 각 간선의 길이는 사인드 32 비트 정수의 변수 내에 들어맞습니다.
각 그래프는 일련의 m+2 줄로 출력되어야 합니다. 이러한 줄들의 첫 줄은 n을 포함하여야 하고 두 번째 줄은 m을 포함하여야 하고, 그 다음 각 m 줄은 간선(0과 n-1로 이루어진 양 끝 점의 정점의 번호)과 그 다음으로 길이를 의미하는 세 정수를 포함하여야 합니다.
힌트
이 그래프에서, 우리의 구현은 정확히 6개의 정점을 처리합니다. 0, 33, 11, 7, 11(다시), 1.