PKU 1847 Tram

• ダイクストラ法
• 一度訪れたintersectionは二度訪れる必要はない
• よって初めから行ける場所とそれ以外の場所でコストを変えてダイクストラをすれば良い

int main() {
	for (int N, A, B; cin >> N >> A >> B; ) {
		int dp[128];
		fill_n(dp, sizeof(dp) / sizeof(dp[0]), INT_MAX / 2);

		vector<int> graph[128];
		for (int i = 1; i <= N; ++i) {
			int K;
			cin >> K;
			for (int k = 0; k < K; ++k) {
				int dest;
				cin >> dest;
				graph[i].push_back(dest);
			}
		}

		priority_queue<pair<int, int> > q;
		q.push(make_pair(0, A));
		dp[A] = 0;
		while (!q.empty()) {
			const int currentCost = -q.top().first;
			const int currentNode = q.top().second;
			q.pop();

			for (vector<int>::iterator it = graph[currentNode].begin(), itEnd = graph[currentNode].end(); it != itEnd; ++it) {
				const int nextCost = currentCost + (it == graph[currentNode].begin() ? 0 : 1);
				const int nextNode = *it;
				if (dp[nextNode] > nextCost) {
					dp[nextNode] = nextCost;
					q.push(make_pair(-nextCost, nextNode));
				}
			}
		}

		if (dp[B] == INT_MAX / 2) {
			dp[B] = -1;
		}

		cout << dp[B] << endl;
	}
}