题目链接：http://codeforces.com/problemset/problem/388/B
大意是用不超过1000个点构造一张边权为1的无向图，使得点1到点2的最短路的个数为给定值k，其中k为不超过1e9的正整数，输出邻接矩阵
构造方法也不止一种
有一种分层构造方法是这样的，
第i层的点与1号点距离为i-1
第一层放置1号点
第二层放置3号和4号点，分别与上一层的1号点相连，他们的最短路为1，且个数也为1
接下来每一层都会比上一层的点数要多1，第i+1层，首先与第i层的前i个点相连，然后第i+1个点与第i层的所有点相连
这样构造的话，最短路个数按照层表示会是
1
1 1
1 1 2
1 1 2 4
1 1 2 4 8
1 1 2 4 8 16
这样下去。主要就是利用了1+2+...+2^n=2^(n+1)-1 再多一个个数为1的点就能凑成下一个2的幂了
其他的构造方法还可以是不断地分出2个岔路，再汇合，再分岔，这样的话每个汇合点也是一个2的幂，但是要注意每个汇合点不能直接连到2号点，因为每个汇合点与1号点距离是不相等的，处理方法可以是往下拖到一条“总线”上，总线末端与2号点相连
下面是第一种构造方式的代码
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream; public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
InputReader in = new InputReader(inputStream);
PrintWriter out = new PrintWriter(outputStream);
Task solver = new Task();
solver.solve(1, in, out);
out.close();
} static class Task {
void addEdge(boolean[][] g, int u, int v) {
g[u][v] = true;
g[v][u] = true;
} public void solve(int testNumber, InputReader in, PrintWriter out) {
int k = in.nextInt();
boolean[][] g = new boolean[1001][10001];
int n = 2;
int from = 0, to = 1;
for (int p = 1, l = 1; p <= k; p <<= 1, l++) {
int nfrom = n;
for (int i = from; i < to; i++) {
addEdge(g, i, n++);
}
for (int i = from; i < to; i++) {
addEdge(g, i, n);
}
from = nfrom;
to = ++n;
}
for (int i = from + 1; i < to; i++) {
if ((k & (1 << i - from - 1)) != 0) {
addEdge(g, i, 1);
}
}
out.println(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
out.print((g[i][j] ? "Y" : "N"));
}
out.println();
}
} } static class InputReader {
private final BufferedReader reader;
private StringTokenizer tokenizer; public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream));
tokenizer = null;
} public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
} public int nextInt() {
return Integer.parseInt(next());
} }
}