#ABC160D. Line++
Line++
题目描述
We have an undirected graph with vertices numbered to and edges as follows:
- For each , there is an edge between Vertex and Vertex .
- There is an edge between Vertex and Vertex .
For each , solve the problem below:
- Find the number of pairs of integers such that the shortest distance between Vertex and Vertex in is .
我们有一个无向图 ,其中有 个顶点,编号为 至 和 条边,如下所示:
- 对于每个 ,顶点 和顶点 之间都有一条边。
- 顶点 与顶点 之间有一条边。
请针对每个 解决下面的问题:
- 求在 中,顶点 与顶点 之间的最短距离为 的整数对 的个数。
输入格式
输入内容按以下格式标准输入:
输出格式
对于顺序中的每一个 ,打印一行包含问题答案的内容。
样例 #1
样例输入 #1
5 2 4
样例输出 #1
5
4
1
0
样例 #2
样例输入 #2
3 1 3
样例输出 #2
3
0
样例 #3
样例输入 #3
7 3 7
样例输出 #3
7
8
4
2
0
0
样例 #4
样例输入 #4
10 4 8
样例输出 #4
10
12
10
8
4
1
0
0
0
说明
数据规模与约定
- 所有输入值均为整数。
样例 解释
该输入的图形如下
有五个线对 ,使得顶点 与顶点 之间的最短距离为 : .
有四对组合 ,使得顶点 与顶点 之间的最短距离为 : .
有一对顶点 ,使得顶点 与顶点 之间的最短距离为 : .
没有一对 使得顶点 与顶点 之间的最短距离为 。
样例 解释
该输入的图表如下