UVa 567 Risk

題意:
　　1~19行，每行第一個數字表示後面會輸入幾個數字，而第i行表示第i個點能連到哪些點，第20行只有一個數字表示之後有幾個測試資料，每個測試資料有兩個數字：起點和終點，求出最短距離。

想法：
　　BFS題目，將每個點依序建立連結後，使用BFS並依題目要求輸出即可。

	#include <cstdio>
	#include <vector>
	#include <queue>
	using namespace std;
	int BFS(int Start, int End, vector<int> toPoint[])
	{
	int visit[21] = {0};
	queue<int> Q;
	Q.push(Start);
	while (!Q.empty()) {
	int cur = Q.front();
	Q.pop();
	for (int nxt : toPoint[cur]) {
	if (visit[nxt] == 0) {
	visit[nxt] = visit[cur] + 1;
	if (nxt == End) return visit[nxt];
	Q.push(nxt);
	}
	}
	}
	return -1;
	}
	int main()
	{
	// freopen("input.txt","rt",stdin);
	int N, i, j, point, Case = 1;
	while (scanf("%d", &N) != EOF) {
	vector<int> toPoint[21];
	for (j=0; j<N; ++j){ // 輸入第1個點
	scanf("%d", &point);
	toPoint[1].push_back(point);
	toPoint[point].push_back(1);
	}
	for (i=2; i<=19; ++i) { // 輸入第2~19個點
	scanf("%d", &N);
	for (j=0; j<N; ++j) {
	scanf("%d", &point);
	toPoint[i].push_back(point);
	toPoint[point].push_back(i);
	}
	}
	scanf("%d", &N);
	printf("Test Set #%d\n", Case++);
	while (N--) {
	int start_point, end_point;
	scanf("%d%d", &start_point, &end_point);
	printf("%2d to %2d: %d\n", start_point, end_point,
	BFS(start_point, end_point, toPoint));
	}
	printf("\n");
	}
	return 0;
	}

view raw [UVa] 567 Risk.cpp hosted with ❤ by GitHub