[2018 SCPC 2차 예선]
Bitonic Paths
간선 마다 양의 가중치가 주어진 방향성이 없는 그래프가 있다고 하자.
이 그래프에서 두 정점을 연결하는 경로의 길이는 경로를 구성하는 간선들의 가중치의 합으로 정의되고, 최단 경로를 구하는 효율적인 알고리즘이 알려져 있다.
정점 \(s\) 로부터 정점 \(t\) 까지를 연결하는 경로에 대해, 이 경로를 구성하는 간선들의 가중치가 \(s\) 로부터 \(t\) 까지 경로를 따른 순서대로 같거나 증가하면, 이러한 경로를 “단조 증가 경로”라고 하자.
반대로, 이러한 경로를 구성하는 간선들의 가중치가 \(s\) 로부터 \(t\) 까지 경로를 따른 순서대로 같거나 감소하면 이러한 경로를 “단조 감소 경로”라고 하자.
경로가 하나의 간선으로 구성된 경우에는 단조 증가 경로 이면서 동시에 단조 감소 경로이다.
이 두가지 정의를 조합하여 다음과 같이 새로운 형태의 경로를 정의할 수 있다.
정점 \(s\) 로부터 정점 \(t\) 까지를 연결하는 경로에 대해, 이 경로상의 한 정점 \(v\) 를 기준으로, \(s\) 로부터 \(v\) 까지 부분 경로가 단조 증가 경로이고 \(v\) 로부터 \(t\) 까지 부분 경로가 단조 감소 경로라면 이러한 경로를 “바이토닉 경로” 라고 하자.
이 때, \(v\)는 \(s\) 혹은 \(t\) 일 수도 있으며, 부분 경로는 정점 하나로만 구성될 수 있다.
<그림 1>의 왼쪽 그림은 간선 마다 양의 가중치가 주어진 방향성이 없는 그래프이다.
<그림 1>의 오른쪽 그림은 1번 정점과 6번 정점을 연결하는 바이토닉 경로 1-2-3-4-6을 보여준다.
이 경로는 3번 정점을 기준으로 단조 증가 경로인 1-2-3과 단조 감소 경로인 3-4-6 으로 구성되기 때문에 바이토닉 경로가 되고 경로의 길이는 12이다.
이 경로는 4번 정점을 기준으로 단조 증가 경로인 1-2-3-4와 단조 감소 경로인 4-6 으로 구성되는 바이토닉 경로라고도 할 수 있다.
경로 1-6 의 경우에도 1번 정점을 기준으로 바이토닉 경로가 된다.
<그림 1>의 왼쪽 그래프에서 1번과 6번 정점을 연결하는 간선과 함께 2번과 3번 정점을 연결하는 간선을 지우고 나면 1번 정점과 6번 정점을 연결하는 바이토닉 경로는 존재하지 않는다.
<그림 1>
주어진 그래프에서 두 노드를 연결하는 최단 바이토닉 경로의 길이를 계산하여 출력 하시오.
- 제한시간: 전체 테스트 케이스는 40개 이하이며, 전체 수행 시간은 3초 이내. (Java 6초 이내)
제한 시간을 초과하면 제출한 소스코드의 프로그램이 즉시 종료되며,
그때까지 수행한 결과에서 테스트 케이스를 1개 그룹 이상 통과하였더라도 점수는 0점이 됩니다.
그러나, 제한 시간을 초과하더라도 테스트 케이스를 1개 그룹 이상 통과하였다면 '부분 점수(0< 점수< 만점)'를 받을 수 있으며,
이를 위해서는, C / C++ 에서 "printf 함수" 사용할 경우, 프로그램 시작부분에서 "setbuf(stdout, NULL);"를 한번만 사용하십시오.
C++에서는 "setbuf(stdout, NULL);"와 "printf 함수" 대신 "cout"를 사용하고, Java에서는 "System.out.println"을 사용하시면,
제한 시간을 초과하더라도 '부분 점수'를 받을 수 있습니다.
※ 언어별 기본 제공 소스코드 내용 참고
만약, 제한 시간을 초과하지 않았는데도 '부분 점수'를 받았다면, 일부 테스트 케이스를 통과하지 못한 경우 입니다.
- 메모리 사용 제한 : heap, global, static 총계 256MB, stack 1MB
- 제출 제한 : 최대 10회 (제출 횟수를 반영하여 순위 결정 → 동점자의 경우 제출 횟수가 적은 사람에게 높은 순위 부여)
입력
입력 파일에는 여러 테스트 케이스가 포함될 수 있다.
파일의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 \(T\) 가 주어지고,
이후 차례로 \(T\) 개의 테스트 케이스가 주어진다. (\(1 ≤ T ≤ 40\))
각 테스트 케이스의 첫 줄에는 두 개의 정수 \(N\) (\(3≤N≤100,000\))과 \(M\) (\(3≤M≤100,000\))이 주어지는데, 각각 그래프의 정점의 개수와 간선의 개수를 의미한다.
다음 이어지는 \(M\) 개의 줄 각각에는 3 개의 자연수 \(i,j,k\) 가 순서대로 주어지는데, \(i\) 번 정점과 \(j\)번 정점을 연결하는 간선의 가중치가 k 라는 것을 의미한다. (\(1≤i,j≤N\), \(1≤k≤200,000\))
같은 정점을 연결하는 간선은 없으며, 서로 다른 두 정점을 연결하는 간선은 최대 하나이다.
시작 정점은 1 이고 도착 정점은 \(N\) 이다.
- 점수 : 최대 10회 제출하여 취득한 각각의 점수 중에서 최대 점수 (만점 200점)
주어지는 테스트 케이스 데이터들의 그룹은 아래와 같으며,
각 그룹의 테스트 케이스를 모두 맞추었을 때 해당되는 부분 점수를 받을 수 있다.
ㆍ 그룹 1 (55점) : 이 그룹의 테스트 케이스에서는 \(N,M≤1,000\)이다.
ㆍ 그룹 2 (84점) : 이 그룹의 테스트 케이스에서는 모든 간선의 가중치는 서로 다르다.
ㆍ 그룹 3 (61점) : 이 그룹의 테스트 케이스에서는 추가적인 제약 사항이 없다.
출력
각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며,
각 테스트 케이스마다 첫 줄에는 “Case #C”를 출력하여야 한다.
이때 C는 테스트 케이스의 번호이다.
시작 정점부터 도착 정점 까지를 연결하는 최단 바이토닉 경로의 길이를 출력하시오.
이러한 경로가 없을 경우 -1을 출력하시오.
입출력예
| 입력 |
|---|
| 2 3 3 1 2 3 1 3 10 2 3 6 6 7 1 2 1 1 6 15 2 3 3 2 5 6 3 4 6 3 5 5 4 6 2 |
| 출력 |
|---|
| Case #1 9 Case #2 12 |