Circuits
시간 제한2초메모리 제한1024 MB
정점이 18개 이하인 방향 그래프에서 도시 1에서 시작하고 끝나는 해밀턴 회로를 사전순으로 나열했을 때 K번째 회로를 구한다.
문제
Jane and Joe are planning their winter vacation. They already have a list with N cities that they want to visit and another list with M flights connecting the cities.
Since Jane and Joe just won the lottery, instead of finding the cheapest circuit that visits all the cities exactly once, they want to choose the Kth such circuit in lexicographic order because this is their lucky number.
입력
The first line contains three integers N, M and K.
The following M lines contain the list of flight connections in the format: u v meaning that there is a flight leaving from city u and arriving in city v.
출력
The first line contains N + 1 numbers representing the circuit that Jane and Joe want to take, if it exists. Otherwise print a single number: 0 .
제한
- A circuit starts and finishes in city number 1 (Jane and Joe's home city).
- A flight connection allows them to fly from city u to city v but not the other way around.
- Two circuits are different if the order the cities are visited is different.
- 3 ≤ N ≤ 18.
- 0 ≤ M ≤ N ⋅ (N − 1).
- 1 ≤ K ≤ 1018.
- 1 ≤ u, v ≤ N, u ≠ v for all flights.
힌트
There are 3 possible circuits. In lexicographic order, they are:
- 1 2 4 3 1
- 1 3 4 2 1
- 1 4 2 3 1