漂洋过海来看你 Description BMan和hyx住在一个神奇的国度，这个国度有N个城市，这N个城市间只有N-1条路把这个N个城市连接起来。 现在BMan在第S号城市，他经常想起那个一起AC过的队友hyx，记忆它总是慢慢的累积，在他心中无法抹去，可是他并不知道hyx 在哪个城市，所以他决定用尽半年的积蓄漂洋过海去找hyx，现在BMan很想知道如果他想去hyx所在的第X号城市，必须经过的前 一个城市是第几号城市（放心，由于心系队友，BMan是不会选择走重复的路的~） Input 第一行输入一个整数T表示测试数据共有T(1<=T<=10)组 每组测试数据的第一行输入一个正整数N(1<=N<=1000)和一个正整数S(1<=S<=1000)，N表示城市的总数，S是BMan所在城市的编号 随后的N-1行，每行有两个正整数a,b(1<=a,b<=N)，表示第a号城市和第b号城市之间有一条路连通。 Output 每组测试数据输N个正整数，，其中，第i个数表示从S走到i号城市，必须要经过的上一个城市的编号（其中i=S时，请输出-1） Sample Input 1 10 1 1 9 1 8 8 10 10 3 8 6 1 2 10 4 9 5 3 7 Sample Output -1 1 10 10 9 8 3 1 1 8
最短路或dfs均可做
最短路代码：
;const int MAXV = 4010;const int inf = 10000000;int map[MAXV][MAXV];int d[MAXV];bool vis[MAXV];int n, m;int pre[MAXV];void dijkstra(int s){for (int i = 1; i <= n; i++){vis[i] = 0;d[i] = map[s][i];}while (1){int min = inf, v = -1;for (int i = 1; i <= n; i++)if (!vis[i] && d[i]<min){v = i;min = d[i];}if (v == -1)break;vis[v] = 1;for (int i = 1; i <= n; i++)if (!vis[i] && d[i] >= d[v] + map[v][i]){d[i] = map[v][i] + d[v];pre[i] = v;}}}int t, a, b;int main(){scanf(“%d”, &t);while (t–){scanf(“%d%d”, &n, &m);for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++){if (i == j)map[i][i] = 0;elsemap[i][j] = map[j][i] = inf;}memset(pre, 0, sizeof(pre));pre[m] = -1;for (int i = 1; i < n; i++){scanf(“%d%d”, &a, &b);map[a][b] = map[b][a] = 1;}dijkstra(m);for (int i = 1; i < n; i++)printf(“%d “, pre[i]);printf(“%d\n”, pre[n]);}return 0;}
dfs代码：
;const int MAXV = 4010;const int inf = 10000000;int map[MAXV][MAXV];int d[MAXV];bool vis[MAXV];int n, m;int pre[MAXV];int t, a, b;void dfs(int s){vis[s] = 1;for (int i = 1; i <= n; i++){if (!vis[i] && map[s][i] == 1){pre[i] = s;vis[i] = 1;dfs(i);}}}int main(){scanf(“%d”,&t);while (t–){memset(vis,0,sizeof(vis));scanf(“%d%d”,&n,&m);memset(map,0,sizeof(map));memset(pre,0,sizeof(pre));pre[m] = -1;for (int i = 1; i < n; i++){scanf(“%d%d”,&a,&b);map[a][b] = map[b][a] = 1;}dfs(m);for (int i = 1; i < n; i++)printf(“%d “,pre[i]);printf(“%d\n”,pre[n]);}return 0;}
空虚无聊的时候就读书，但一定得有自己的生活目标和计划。
