백준(BOJ) 16166 서울의 지하철 *

# DP

#include <iostream>
#include <cstdio>
#include <vector>
#include <deque>
#include <string.h>
#include <algorithm>
using namespace std;
long long ans;

int n;
int arr[11][11];
int dp[11];
vector <int> link[11];

int main() {
	memset(arr, -1, sizeof(arr));
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		int k;
		scanf("%d", &k);
		for(int j=0 ; j<k ; j++)
			scanf("%d", arr[i] + j);
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < 10; j++) {
			if (arr[i][j] == -1)
				break;
			for (int x = i + 1; x <= n; x++) {
				for (int y = 0; y < 10; y++) {
					if (arr[x][y] == -1)
						break;
					if (arr[i][j] == arr[x][y]) {
						link[i].push_back(x);
						link[x].push_back(i);
					}
				}
			}
		}
	 }

	deque <int > dq;
	memset(dp, -1, sizeof(dp));
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < 10; j++) {
			if (arr[i][j] == -1)
				break;
			if (arr[i][j] == 0) {
				dp[i] = 0;
				dq.push_back(i);
			}
		}
	}
	while (!dq.empty()) {
		int now = dq.front();
		dq.pop_front();
		for (int next : link[now]) {
			if (dp[next] == -1 || dp[next] > dp[now] + 1) {
				dp[next] = dp[now] + 1;
				dq.push_back(next);
			}
		}
	}
	int t;
	scanf("%d", &t);
	int ans = -1;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < 10; j++) {
			if (arr[i][j] == -1)
				break;
			if (arr[i][j] == t) {
				if (ans == -1)
					ans = dp[i];
				else
					ans = min(ans, dp[i]);
			}
		}
	}
	printf("%d\n", ans);
}