123 lines
3.3 KiB
Markdown
123 lines
3.3 KiB
Markdown
Q1
|
||
```
|
||
请编写程序创建一个有向图。有向图中包含n个顶点，编号为0至n-1。
|
||
|
||
输入格式:
|
||
输入第一行为两个正整数n和e，分别表示图的顶点数和边数，其中n不超过20000，e不超过20000。接下来e行表示每条边的信息，每行为3个非负整数a、b、c，其中a和b表示该边的端点编号，c表示权值。各边并非按端点编号顺序排列。
|
||
|
||
输出格式:
|
||
按顶点编号递增顺序输出每个顶点引出的边，每个顶点占一行，若某顶点没有引出边，则不输出。每行表示一个顶点引出的所有边，格式为a:(a,b,w)……，表示有向边a->b的权值为w，a引出的多条边按编号b的递增序排列。
|
||
|
||
输入样例:
|
||
7 7
|
||
0 1 5
|
||
0 3 7
|
||
0 6 6
|
||
1 2 4
|
||
2 5 1
|
||
3 5 3
|
||
6 5 4
|
||
|
||
输出样例:
|
||
0:(0,1,5)(0,3,7)(0,6,6)
|
||
1:(1,2,4)
|
||
2:(2,5,1)
|
||
3:(3,5,3)
|
||
6:(6,5,4)
|
||
|
||
代码长度限制
|
||
16 KB
|
||
时间限制
|
||
500 ms
|
||
内存限制
|
||
20 MB
|
||
栈限制
|
||
8192 KB
|
||
```
|
||
|
||
Q2
|
||
```
|
||
唐僧被妖精抓到了妖洞里，悟空前往解救。妖洞由n行m列单元格组成。有的单元格是空地，可以走；有的单元格处是墙壁，不能走。假定悟空只可以朝上、下、左、右四个方向走，不能斜着走，悟空每行进一个位置（单元格）需要1分钟。此外，悟空有一种超能力，可以在1分钟瞬时移动最多T步（即1分钟行进最多T个单元格），但受体力限制，这种超能力只能使用一次。给定妖洞地图、悟空的位置、唐僧的位置，请编写程序计算悟空解救唐僧所需要的最短时间。
|
||
image.png
|
||
|
||
输入格式:
|
||
输入包含多组数据。每组数据第一行是3个整数n、m、T (1≤ n, m, T ≤100)，含义如题目所述；接下来是n行，每行m个数字，表示整个地图。空地格子用0表示，墙壁用1表示，悟空所在位置用3表示，唐僧的位置用4表示。
|
||
|
||
输出格式:
|
||
对于每组数据，如果悟空能够解救到唐僧，输出一个整数，表示悟空到唐僧所在位置所需的最短时间，如果不能到达唐僧所在位置，输出“can not save”。
|
||
|
||
输入样例1:
|
||
5 5 2
|
||
1 0 1 1 1
|
||
1 0 4 1 0
|
||
1 0 0 1 0
|
||
0 0 0 1 0
|
||
1 0 3 0 1
|
||
5 5 3
|
||
3 0 1 1 1
|
||
1 0 1 1 0
|
||
1 0 1 1 0
|
||
0 0 0 1 0
|
||
1 0 1 0 4
|
||
|
||
输出样例1:
|
||
2
|
||
can not save
|
||
|
||
输入样例2:
|
||
7 8 5
|
||
1 0 1 1 1 1 1 0
|
||
1 0 4 1 0 0 3 0
|
||
1 0 0 1 0 0 0 0
|
||
0 0 1 0 0 1 0 1
|
||
1 0 0 0 1 1 0 0
|
||
0 1 0 0 0 0 0 0
|
||
0 0 0 0 0 0 0 0
|
||
|
||
输出样例2:
|
||
8
|
||
|
||
代码长度限制
|
||
16 KB
|
||
时间限制
|
||
10 ms
|
||
内存限制
|
||
64 MB
|
||
栈限制
|
||
8192 KB
|
||
```
|
||
|
||
Q3
|
||
```
|
||
编写程序对给定的有向图（不一定连通）进行深度优先遍历，图中包含n个顶点，编号为0至n-1。本题限定在深度优先遍历过程中，如果同时出现多个待访问的顶点，则优先选择编号最小的一个进行访问，以顶点0为遍历起点。
|
||
|
||
输入格式:
|
||
输入第一行为两个整数n和e，分别表示图的顶点数和边数，其中n不超过20000，e不超过50。接下来e行表示每条边的信息，每行为两个整数a、b，表示该边的端点编号，但各边并非按端点编号顺序排列。
|
||
|
||
输出格式:
|
||
输出为一行整数，每个整数后一个空格，即该有向图的深度优先遍历结点序列。
|
||
|
||
输入样例1:
|
||
3 3
|
||
0 1
|
||
1 2
|
||
0 2
|
||
输出样例1:
|
||
0 1 2
|
||
输入样例2:
|
||
4 4
|
||
0 2
|
||
0 1
|
||
1 2
|
||
3 0
|
||
输出样例2:
|
||
0 1 2 3
|
||
代码长度限制
|
||
16 KB
|
||
时间限制
|
||
50 ms
|
||
内存限制
|
||
64 MB
|
||
栈限制
|
||
65536 KB
|
||
``` |