liuchuo – 第112页 – 我不管，反正我最萌～

第七届蓝桥杯省赛第八题四平方和

四平方和定理，又称为拉格朗日定理：
每个正整数都可以表示为至多4个正整数的平方和。
如果把0包括进去，就正好可以表示为4个数的平方和。

比如：
5 = 0^2 + 0^2 + 1^2 + 2^2
7 = 1^2 + 1^2 + 1^2 + 2^2
（^符号表示乘方的意思）

对于一个给定的正整数，可能存在多种平方和的表示法。
要求你对4个数排序：
0 <= a <= b <= c <= d
并对所有的可能表示法按 a,b,c,d 为联合主键升序排列，最后输出第一个表示法

程序输入为一个正整数N (N<5000000)
要求输出4个非负整数，按从小到大排序，中间用空格分开

例如，输入：
5
则程序应该输出：
0 0 1 2

再例如，输入：
12
则程序应该输出：
0 2 2 2

再例如，输入：
773535
则程序应该输出：
1 1 267 838

资源约定：
峰值内存消耗 < 256M
CPU消耗 < 3000ms

分析：直接四层循环可能会超时，可以考虑先将两个数能构成的平方和保存在map里面，如果在前两层循环的时候，发现剩下的数并不能由两个数的平方构成，就直接continue跳过～否则就判断第三层循环，然后用sqrt(num – a * a – b * b – c * c)算出最后一个数temp，看它是否为整数～如果是整数就输出～并且退出程序～

#include <iostream>
#include <cmath>
#include <map>
using namespace std;
int main() {
    int num;
    cin >> num;
    int n = sqrt(num);
    map<int, int> m;
    for (int a = 0; a <= n; a++) {
        for (int b = a; b <= n; b++) {
            m[a * a + b * b] = 1;
        }
    }
    for (int a = 0; a <= n; a++) {
        for (int b = a; b <= n; b++) {
            if (m[num - a * a - b * b] != 1) continue;
            for (int c = b; c <= n; c++) {
                double temp = sqrt(num - a * a - b * b - c * c);
                if(temp == (int)temp) {
                    cout << a << " " << b << " " << c << " " << (int)temp;
                    return 0;
                }
            }
        }
    }
    return 0;
}

#include <iostream>

#include <cmath>

#include <map>

using namespace std;

int main() {

int num;

cin >> num;

int n = sqrt(num);

map<int, int> m;

for (int a = 0; a <= n; a++) {

for (int b = a; b <= n; b++) {

m[a * a + b * b] = 1;

}

for (int a = 0; a <= n; a++) {

for (int b = a; b <= n; b++) {

if (m[num - a * a - b * b] != 1) continue;

for (int c = b; c <= n; c++) {

double temp = sqrt(num - a * a - b * b - c * c);

if(temp == (int)temp) {

cout << a << " " << b << " " << c << " " << (int)temp;

return 0;

}

return 0;

}

第七届蓝桥杯省赛第七题剪邮票

剪邮票如【图1.jpg】, 有12张连在一起的12生肖的邮票。

现在你要从中剪下5张来，要求必须是连着的。
（仅仅连接一个角不算相连）
比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。

请你计算，一共有多少种不同的剪取方法。

分析：i1、i2、i3、i4和i5为枚举要剪下的5个数，对这五个数构成的连通性进行dfs判断，如果dfs后测得从i1出发从上下左右四个方向上深度优先搜索遍历为i2～i5之间的所有点，cnt标记i5能够走到的是i1～i5这些点的个数，如果cnt == 5就说明是连在一起的，注意从4和8向右行走走不到5和9，并且从5和9出发向左行走走不到4和8～所以遇到index == 4或者index == 8并且是向右走的时候continue～（index == 5和9并向左走同理～）将result加一～累加得到的result就是结果116～

#include <iostream>
using namespace std;
int dis[4] = {-1, 1, -4, 4}, visit[13];
int i1, i2, i3, i4, i5, cnt, result = 0;
void dfs(int index) {
    if (cnt >= 5) return;
    for (int i = 0; i < 4; i++) {
        if ((dis[i] == 1 && (index == 4 || index == 8)) || (dis[i] == -1 && (index == 5 || index == 9))) continue;
        int t = index + dis[i];
        if (t >= 1 && t <= 12 && visit[t] == 0 && (t == i2 || t == i3 || t == i4 || t == i5)) {
            visit[t] = 1;
            cnt++;
            dfs(t);
        }
    }
}
int main() {
    for (i1 = 1; i1 <= 12 - 4; i1++) {
        for (i2 = i1 + 1; i2 <= 12 - 3; i2++) {
            for (i3 = i2 + 1; i3 <= 12 - 2; i3++) {
                for (i4 = i3 + 1; i4 <= 12 - 1; i4++) {
                    for (i5 = i4 + 1; i5 <= 12; i5++) {
                        memset(visit, 0, sizeof(visit));
                        cnt = 1;
                        dfs(i1);
                        if (cnt == 5) result++;
                    }
                }
            }
        }
    }
    cout << result;
    return 0;
}

#include <iostream>

using namespace std;

int dis[4] = {-1, 1, -4, 4}, visit[13];

int i1, i2, i3, i4, i5, cnt, result = 0;

void dfs(int index) {

if (cnt >= 5) return;

for (int i = 0; i < 4; i++) {

if ((dis[i] == 1 && (index == 4 || index == 8)) || (dis[i] == -1 && (index == 5 || index == 9))) continue;

int t = index + dis[i];

if (t >= 1 && t <= 12 && visit[t] == 0 && (t == i2 || t == i3 || t == i4 || t == i5)) {

visit[t] = 1;

cnt++;

dfs(t);

}

int main() {

for (i1 = 1; i1 <= 12 - 4; i1++) {

for (i2 = i1 + 1; i2 <= 12 - 3; i2++) {

for (i3 = i2 + 1; i3 <= 12 - 2; i3++) {

for (i4 = i3 + 1; i4 <= 12 - 1; i4++) {

for (i5 = i4 + 1; i5 <= 12; i5++) {

memset(visit, 0, sizeof(visit));

cnt = 1;

dfs(i1);

if (cnt == 5) result++;

}

cout << result;

return 0;

}

第七届蓝桥杯省赛第六题方格填数（next_permutation）

填入0~9的数字。要求：连续的两个数字不能相邻。
（左右、上下、对角都算相邻）
一共有多少种可能填写的方案？
请填写表示方案数目的整数～

分析：从左到右从上到下标为0～9，将a[10]中的数字依次填入，所以只要将a数组从0123456789一直全排列试到9876543210，测试每一个结果是否满足，满足条件的次数累加得到的就是方案数目～答案是1580～

#include <iostream>
#include <algorithm>
using namespace std;
int a[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
bool judge(int i, int j) {
    return (a[i] - a[j] == 1 || a[i] - a[j] == -1);
}
bool func() {
    if (judge(0, 1) || judge(0, 3) ||judge(0, 4) ||judge(0, 5) ||judge(1, 2)||judge(1, 4) ||judge(1, 5) ||judge(1,6) ||judge(2, 5) ||judge(2, 6) ||judge(3, 4) ||judge(3, 7) ||judge(3, 8) ||  judge(4, 5) ||judge(4, 7) || judge(4, 8) ||judge(4, 9) ||judge(5, 6) ||judge(5, 8) || judge(5, 9) || judge(6, 9)|| judge(7, 8) ||judge(8, 9))
        return false;
    return true;
}
int main() {
    int n = 1, cnt = 0;
    for (int i = 1; i <= 10; i++)
        n = n * i;
    for (int i = 1; i < n; i++) {
        next_permutation(a, a+10);
        if (func() == true)
            cnt++;
    }
    cout << cnt;
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int a[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

bool judge(int i, int j) {

return (a[i] - a[j] == 1 || a[i] - a[j] == -1);

}

bool func() {

if (judge(0, 1) || judge(0, 3) ||judge(0, 4) ||judge(0, 5) ||judge(1, 2)||judge(1, 4) ||judge(1, 5) ||judge(1,6) ||judge(2, 5) ||judge(2, 6) ||judge(3, 4) ||judge(3, 7) ||judge(3, 8) || judge(4, 5) ||judge(4, 7) || judge(4, 8) ||judge(4, 9) ||judge(5, 6) ||judge(5, 8) || judge(5, 9) || judge(6, 9)|| judge(7, 8) ||judge(8, 9))

return false;

return true;

}

int main() {

int n = 1, cnt = 0;

for (int i = 1; i <= 10; i++)

n = n * i;

for (int i = 1; i < n; i++) {

next_permutation(a, a+10);

if (func() == true)

cnt++;

}

cout << cnt;

return 0;

}

蓝桥杯 ALGO-149 算法训练 5-2求指数

问题描述
　　已知n和m，打印n^1，n^2，…，n^m。要求用静态变量实现。n^m表示n的m次方。已知n和m，打印n^1，n^2，…，n^m。要求用静态变量实现。n^m表示n的m次方。（每行显示5个数，每个数宽为12，右对齐）
样例输入
一个满足题目要求的输入范例。
例：
3 8
样例输出
与上面的样例输入对应的输出。
例：

数据规模和约定
　　输入数据中每一个数的范围。
　　例：n^m小于int 的表示范围。

分析：用静态变量表示result和m，每次将m减一，result累乘并输出，以%12d的形式输出～

#include <cstdio>
static int result = 1, m;
int n, rest, flag = 0;
void func() {
    result *= n;
    if (flag == 1 && (m - rest) % 5 == 0) 
        printf("\n");
    flag = 1;
    m--;
    printf("%12d", result);
}
int main() {
    scanf("%d%d", &n, &m);
    rest = m % 5;
    while (m != 0)
        func();
    return 0;
}

#include <cstdio>

static int result = 1, m;

int n, rest, flag = 0;

void func() {

result *= n;

if (flag == 1 && (m - rest) % 5 == 0)

printf("\n");

flag = 1;

m--;

printf("%12d", result);

}

int main() {

scanf("%d%d", &n, &m);

rest = m % 5;

while (m != 0)

func();

return 0;

}

CCCC-GPLT L3-014. 周游世界团体程序设计天梯赛

周游世界是件浪漫事，但规划旅行路线就不一定了…… 全世界有成千上万条航线、铁路线、大巴线，令人眼花缭乱。所以旅行社会选择部分运输公司组成联盟，每家公司提供一条线路，然后帮助客户规划由联盟内企业支持的旅行路线。本题就要求你帮旅行社实现一个自动规划路线的程序，使得对任何给定的起点和终点，可以找出最顺畅的路线。所谓“最顺畅”，首先是指中途经停站最少；如果经停站一样多，则取需要换乘线路次数最少的路线。

输入格式：

输入在第一行给出一个正整数N（<= 100），即联盟公司的数量。接下来有N行，第i行（i=1, …, N）描述了第i家公司所提供的线路。格式为：

M S[1] S[2] … S[M]

其中M（<= 100）是经停站的数量，S[i]（i=1, …, M）是经停站的编号（由4位0-9的数字组成）。这里假设每条线路都是简单的一条可以双向运行的链路，并且输入保证是按照正确的经停顺序给出的 —— 也就是说，任意一对相邻的S[i]和S[i+1]（i=1, …, M-1）之间都不存在其他经停站点。我们称相邻站点之间的线路为一个运营区间，每个运营区间只承包给一家公司。环线是有可能存在的，但不会不经停任何中间站点就从出发地回到出发地。当然，不同公司的线路是可能在某些站点有交叉的，这些站点就是客户的换乘点，我们假设任意换乘点涉及的不同公司的线路都不超过5条。

在描述了联盟线路之后，题目将给出一个正整数K（<= 10），随后K行，每行给出一位客户的需求，即始发地的编号和目的地的编号，中间以一空格分隔。

输出格式：

处理每一位客户的需求。如果没有现成的线路可以使其到达目的地，就在一行中输出“Sorry, no line is available.”；如果目的地可达，则首先在一行中输出最顺畅路线的经停站数量（始发地和目的地不包括在内），然后按下列格式给出旅行路线：

Go by the line of company #X1 from S1 to S2.
Go by the line of company #X2 from S2 to S3.
……
其中Xi是线路承包公司的编号，Si是经停站的编号。但必须只输出始发地、换乘点和目的地，不能输出中间的经停站。题目保证满足要求的路线是唯一的。

输入样例：
4
7 1001 3212 1003 1204 1005 1306 7797
9 9988 2333 1204 2006 2005 2004 2003 2302 2001
13 3011 3812 3013 3001 1306 3003 2333 3066 3212 3008 2302 3010 3011
4 6666 8432 4011 1306
4
3011 3013
6666 2001
2004 3001
2222 6666
输出样例：
2
Go by the line of company #3 from 3011 to 3013.
10
Go by the line of company #4 from 6666 to 1306.
Go by the line of company #3 from 1306 to 2302.
Go by the line of company #2 from 2302 to 2001.
6
Go by the line of company #2 from 2004 to 1204.
Go by the line of company #1 from 1204 to 1306.
Go by the line of company #3 from 1306 to 3001.
Sorry, no line is available.

分析：【很简单的，别跑^_^】

一遍DFS即可～DFS过程中要维护两个变量：minCnt-中途经停的最少的站; minTransfer-需要换乘的最小次数～
0.可以这样计算出一条线路的换乘次数：在line[10000][10000]的数组中保存每两个相邻站中间的线路是几号线～从头到尾遍历最终保存的路径，preLine为前一小段的线路编号，如果当前的结点和前一个结点组成的这条路的线路编号和preLine不同，说明有一个换乘，就将cnt+1，最后遍历完累加的cnt即是换乘的次数～
1.可以这样计算出一条线路中途停站的次数：在dfs的时候有个变量cnt，表示当前路线是所需乘的第几个站，每次dfs时候将cnt+1表示向下遍历一层～cnt就是当前中途停站的次数～
2.可以这样输出结果：和计算线路换乘次数的思路一样，每当preLine和当前Line值不同的时候就输出一句话～保存preTransfer表示上一个换乘站，最后不要忘记输出preTransfer和最后一个站之间的路即使最后一个站并不是换乘站～

#include <cstdio>
#include <vector>
using namespace std;
vector<vector<int>> v(10000);
int line[10000][10000], visit[10000];
vector<int> path, tempPath;
int transferCnt(vector<int> a) {
    int cnt = -1, preLine = 0;
    for (int i = 1; i < a.size(); i++) {
        if (line[a[i-1]][a[i]] != preLine) cnt++;
        preLine = line[a[i-1]][a[i]];
    }
    return cnt;
}
void dfs(int node, int end, int cnt, int &minCnt, int &minTransfer) {
    if (node == end && (cnt < minCnt || (cnt == minCnt && transferCnt(tempPath) < minTransfer))) {
        minCnt = cnt;
        minTransfer = transferCnt(tempPath);
        path = tempPath;
    }
    if (node == end) return;
    for (int i = 0; i < v[node].size(); i++) {
        if (visit[v[node][i]] == 0) {
            visit[v[node][i]] = 1;
            tempPath.push_back(v[node][i]);
            dfs(v[node][i], end, cnt + 1, minCnt, minTransfer);
            visit[v[node][i]] = 0;
            tempPath.pop_back();
        }
    }
}
int main() {
    int n, m, k, pre, temp, a, b;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &m, &pre);
        for (int j = 1; j < m; j++) {
            scanf("%d", &temp);
            v[pre].push_back(temp);
            v[temp].push_back(pre);
            line[pre][temp] = line[temp][pre] = i + 1;
            pre = temp;
        }
    }
    scanf("%d", &k);
    for (int i = 0; i < k; i++) {
        scanf("%d%d", &a, &b);
        int minCnt = 99999, minTransfer = 99999;
        tempPath.clear();
        tempPath.push_back(a);
        visit[a] = 1;
        dfs(a, b, 0, minCnt, minTransfer);
        visit[a] = 0;
        if (minCnt == 99999) {
            printf("Sorry, no line is available.\n");
            continue;
        }
        printf("%d\n", minCnt);
        int preLine = 0, preTransfer = a;
        for (int j = 1; j < path.size(); j++) {
            if (line[path[j-1]][path[j]] != preLine) {
                if (preLine != 0) printf("Go by the line of company #%d from %04d to %04d.\n", preLine, preTransfer, path[j-1]);
                preLine = line[path[j-1]][path[j]];
                preTransfer = path[j-1];
            }
        }
        printf("Go by the line of company #%d from %04d to %04d.\n", preLine, preTransfer, b);
    }
    return 0;
}

#include <cstdio>

#include <vector>

using namespace std;

vector<vector<int>> v(10000);

int line[10000][10000], visit[10000];

vector<int> path, tempPath;

int transferCnt(vector<int> a) {

int cnt = -1, preLine = 0;

for (int i = 1; i < a.size(); i++) {

if (line[a[i-1]][a[i]] != preLine) cnt++;

preLine = line[a[i-1]][a[i]];

}

return cnt;

}

void dfs(int node, int end, int cnt, int &minCnt, int &minTransfer) {

if (node == end && (cnt < minCnt || (cnt == minCnt && transferCnt(tempPath) < minTransfer))) {

minCnt = cnt;

minTransfer = transferCnt(tempPath);

path = tempPath;

}

if (node == end) return;

for (int i = 0; i < v[node].size(); i++) {

if (visit[v[node][i]] == 0) {

visit[v[node][i]] = 1;

tempPath.push_back(v[node][i]);

dfs(v[node][i], end, cnt + 1, minCnt, minTransfer);

visit[v[node][i]] = 0;

tempPath.pop_back();

}

int main() {

int n, m, k, pre, temp, a, b;

scanf("%d", &n);

for (int i = 0; i < n; i++) {

scanf("%d%d", &m, &pre);

for (int j = 1; j < m; j++) {

scanf("%d", &temp);

v[pre].push_back(temp);

v[temp].push_back(pre);

line[pre][temp] = line[temp][pre] = i + 1;

pre = temp;

}

scanf("%d", &k);

for (int i = 0; i < k; i++) {

scanf("%d%d", &a, &b);

int minCnt = 99999, minTransfer = 99999;

tempPath.clear();

tempPath.push_back(a);

visit[a] = 1;

dfs(a, b, 0, minCnt, minTransfer);

visit[a] = 0;

if (minCnt == 99999) {

printf("Sorry, no line is available.\n");

continue;

}

printf("%d\n", minCnt);

int preLine = 0, preTransfer = a;

for (int j = 1; j < path.size(); j++) {

if (line[path[j-1]][path[j]] != preLine) {

if (preLine != 0) printf("Go by the line of company #%d from %04d to %04d.\n", preLine, preTransfer, path[j-1]);

preLine = line[path[j-1]][path[j]];

preTransfer = path[j-1];

}

printf("Go by the line of company #%d from %04d to %04d.\n", preLine, preTransfer, b);

}

return 0;

}

喵喵喵～

PAT 1131. Subway Map (30) -甲级（图的遍历，DFS）

In the big cities, the subway systems always look so complex to the visitors. To give you some sense, the following figure shows the map of Beijing subway. Now you are supposed to help people with your computer skills! Given the starting position of your user, your task is to find the quickest way to his/her destination.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (< =100), the number of subway lines. Then N lines follow, with the i-th (i = 1, …, N) line describes the i-th subway line in the format:

M S[1] S[2] … S[M]

where M (<= 100) is the number of stops, and S[i]’s (i = 1, … M) are the indices of the stations (the indices are 4-digit numbers from 0000 to 9999) along the line. It is guaranteed that the stations are given in the correct order — that is, the train travels between S[i] and S[i+1] (i = 1, …, M-1) without any stop.

Note: It is possible to have loops, but not self-loop (no train starts from S and stops at S without passing through another station). Each station interval belongs to a unique subway line. Although the lines may cross each other at some stations (so called “transfer stations”), no station can be the conjunction of more than 5 lines.

After the description of the subway, another positive integer K (<= 10) is given. Then K lines follow, each gives a query from your user: the two indices as the starting station and the destination, respectively.

The following figure shows the sample map.
Note: It is guaranteed that all the stations are reachable, and all the queries consist of legal station numbers.

Output Specification:

For each query, first print in a line the minimum number of stops. Then you are supposed to show the optimal path in a friendly format as the following:

Take Line#X1 from S1 to S2.
Take Line#X2 from S2 to S3.
……
where Xi’s are the line numbers and Si’s are the station indices. Note: Besides the starting and ending stations, only the transfer stations shall be printed.

If the quickest path is not unique, output the one with the minimum number of transfers, which is guaranteed to be unique.

Sample Input:

4
7 1001 3212 1003 1204 1005 1306 7797
9 9988 2333 1204 2006 2005 2004 2003 2302 2001
13 3011 3812 3013 3001 1306 3003 2333 3066 3212 3008 2302 3010 3011
4 6666 8432 4011 1306
3
3011 3013
6666 2001
2004 3001

Sample Output:

2
Take Line#3 from 3011 to 3013.
10
Take Line#4 from 6666 to 1306.
Take Line#3 from 1306 to 2302.
Take Line#2 from 2302 to 2001.
6
Take Line#2 from 2004 to 1204.
Take Line#1 from 1204 to 1306.
Take Line#3 from 1306 to 3001.

题目大意：找出一条路线，使得对任何给定的起点和终点，可以找出中途经停站最少的路线；如果经停站一样多，则取需要换乘线路次数最少的路线～
【很简单的，别跑^_^】
分析：一遍DFS即可～DFS过程中要维护两个变量：minCnt-中途经停的最少的站; minTransfer-需要换乘的最小次数～
0.可以这样计算出一条线路的换乘次数：在line[10000][10000]的数组中保存每两个相邻站中间的线路是几号线～从头到尾遍历最终保存的路径，preLine为前一小段的线路编号，如果当前的结点和前一个结点组成的这条路的线路编号和preLine不同，说明有一个换乘，就将cnt+1，最后遍历完累加的cnt即是换乘的次数～
update：由于新的PAT系统中会显示原解法有一个测试用例内存超限，考虑到line[10000][10000]存储的方式太暴力了，所以将line换成了unordered_map<int, int> line存储的方式，第一个int用来存储线路，每次将前四位存储第一个线路，后四位存储第二个线路，使用a[i-1]*10000+a[i]的方式存储，第二个int用来保存两个相邻中间的线路是几号线～
1.可以这样计算出一条线路中途停站的次数：在dfs的时候有个变量cnt，表示当前路线是所需乘的第几个站，每次dfs时候将cnt+1表示向下遍历一层～cnt就是当前中途停站的次数～
2.可以这样输出结果：和计算线路换乘次数的思路一样，每当preLine和当前Line值不同的时候就输出一句话～保存preTransfer表示上一个换乘站，最后不要忘记输出preTransfer和最后一个站之间的路即使最后一个站并不是换乘站～

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
vector<vector<int>> v(10000);
int visit[10000], minCnt, minTransfer, start, end1;
unordered_map<int, int> line;
vector<int> path, tempPath;
int transferCnt(vector<int> a) {
    int cnt = -1, preLine = 0;
    for (int i = 1; i < a.size(); i++) {
        if (line[a[i-1]*10000+a[i]] != preLine) cnt++;
        preLine = line[a[i-1]*10000+a[i]];
    }
    return cnt;
}
void dfs(int node, int cnt) {
    if (node == end1 && (cnt < minCnt || (cnt == minCnt && transferCnt(tempPath) < minTransfer))) {
        minCnt = cnt;
        minTransfer = transferCnt(tempPath);
        path = tempPath;
    }
    if (node == end1) return;
    for (int i = 0; i < v[node].size(); i++) {
        if (visit[v[node][i]] == 0) {
            visit[v[node][i]] = 1;
            tempPath.push_back(v[node][i]);
            dfs(v[node][i], cnt + 1);
            visit[v[node][i]] = 0;
            tempPath.pop_back();
        }
    }
}
int main() {
    int n, m, k, pre, temp;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &m, &pre);
        for (int j = 1; j < m; j++) {
            scanf("%d", &temp);
            v[pre].push_back(temp);
            v[temp].push_back(pre);
            line[pre*10000+temp] = line[temp*10000+pre] = i + 1;
            pre = temp;
        }
    }
    scanf("%d", &k);
    for (int i = 0; i < k; i++) {
        scanf("%d%d", &start, &end1);
        minCnt = 99999, minTransfer = 99999;
        tempPath.clear();
        tempPath.push_back(start);
        visit[start] = 1;
        dfs(start, 0);
        visit[start] = 0;
        printf("%d\n", minCnt);
        int preLine = 0, preTransfer = start;
        for (int j = 1; j < path.size(); j++) {
            if (line[path[j-1]*10000+path[j]] != preLine) {
                if (preLine != 0) printf("Take Line#%d from %04d to %04d.\n", preLine, preTransfer, path[j-1]);
                preLine = line[path[j-1]*10000+path[j]];
                preTransfer = path[j-1];
            }
        }
        printf("Take Line#%d from %04d to %04d.\n", preLine, preTransfer, end1);
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <unordered_map>

using namespace std;

vector<vector<int>> v(10000);

int visit[10000], minCnt, minTransfer, start, end1;

unordered_map<int, int> line;

vector<int> path, tempPath;

int transferCnt(vector<int> a) {

int cnt = -1, preLine = 0;

for (int i = 1; i < a.size(); i++) {

if (line[a[i-1]*10000+a[i]] != preLine) cnt++;

preLine = line[a[i-1]*10000+a[i]];

}

return cnt;

}

void dfs(int node, int cnt) {

if (node == end1 && (cnt < minCnt || (cnt == minCnt && transferCnt(tempPath) < minTransfer))) {

minCnt = cnt;

minTransfer = transferCnt(tempPath);

path = tempPath;

}

if (node == end1) return;

for (int i = 0; i < v[node].size(); i++) {

if (visit[v[node][i]] == 0) {

visit[v[node][i]] = 1;

tempPath.push_back(v[node][i]);

dfs(v[node][i], cnt + 1);

visit[v[node][i]] = 0;

tempPath.pop_back();

}

int main() {

int n, m, k, pre, temp;

scanf("%d", &n);

for (int i = 0; i < n; i++) {

scanf("%d%d", &m, &pre);

for (int j = 1; j < m; j++) {

scanf("%d", &temp);

v[pre].push_back(temp);

v[temp].push_back(pre);

line[pre*10000+temp] = line[temp*10000+pre] = i + 1;

pre = temp;

}

scanf("%d", &k);

for (int i = 0; i < k; i++) {

scanf("%d%d", &start, &end1);

minCnt = 99999, minTransfer = 99999;

tempPath.clear();

tempPath.push_back(start);

visit[start] = 1;

dfs(start, 0);

visit[start] = 0;

printf("%d\n", minCnt);

int preLine = 0, preTransfer = start;

for (int j = 1; j < path.size(); j++) {

if (line[path[j-1]*10000+path[j]] != preLine) {

if (preLine != 0) printf("Take Line#%d from %04d to %04d.\n", preLine, preTransfer, path[j-1]);

preLine = line[path[j-1]*10000+path[j]];

preTransfer = path[j-1];

}

printf("Take Line#%d from %04d to %04d.\n", preLine, preTransfer, end1);

}

return 0;

}

喵呜～