문제
이 문제는 그래프 문제이다.
N개의 정점과 M개의 간선으로 이루어진 연결 그래프에서, 1번 정점에서 N번 정점으로 가는 최단경로를 찾고자 한다. 모든 간선의 길이는 1이다.
이렇게 문제를 내면 마지막 문제가 될 수 없기 때문에, 정수 L과 길이 L의 배열 V가 주어졌을 때, i+1번째로 방문하는 정점은 V[i%L]이 될 수 없고, i번째에서 i+1번째로 이동할 때 V[i%L]에서 V[(i-1)%L]로 갈 수 없다는 조건이 K개 주어진다. 단, 각 정점은 최대 하나의 배열 V에 포함되고, 1번 정점과 N번 정점은 V에 포함되지 않는다.
이러면 풀 수 없는 경우가 너무 많아지기 때문에, N개의 간선을 더 추가하여 모든 i에 대해 i번 정점에서 i번 정점으로 가는 self loop를 추가한다.
이 그래프에서 최단 경로의 길이를 구하여라. 만약 조건을 만족하는 경로가 없다면 "impossible"을 출력하라.
제한: N<=250000, M<=3000000, 3<=L<=1500, L의 합<=2750
입력
첫째 줄에 N과 M이 주어진다.
둘째 줄부터 총 M줄 동안 간선의 두 정점이 주어진다.
그 다음 줄에 K가 주어진다.
그 다음 줄부터 총 K줄 동안 각 조건의 L과 V가 주어진다.
출력
최단 경로의 길이를 출력하여라. 만약 경로가 없다면 "impossible"을 출력하라.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 10점 | N,M<=100000, K=1, L<=125 |
| #2 | 10점 | N,M<=100000, L의 합<=125, 간선이 이어주는 두 정점이 서로 다른 배열 V에 속해있는 경우는 없다. |
| #3 | 10점 | L의 합<=350, L<=200, 간선이 이어주는 두 정점이 서로 다른 배열 V에 속해있는 경우는 없다. |
| #4 | 10점 | 간선이 이어주는 두 정점이 서로 다른 배열 V에 속해있는 경우는 없다. |
| #5 | 20점 | L의 합<=125 |
| #6 | 20점 | L의 합<=350, L<=200 |
| #7 | 20점 | 추가 조건이 없다. |
예제 #1
6 6
1 2
2 3
3 4
4 5
5 2
5 6
1
4 3 2 5 4
4
예제 #2
11 13
1 2
2 3
3 4
4 2
3 5
5 6
6 7
7 5
6 8
8 9
9 10
10 8
9 11
3
3 4 2 3
3 7 6 5
3 10 8 9
impossible
로그인해야 코드를 작성할 수 있어요.