这道题的意思大致就是给你一个数k(k<=10^9)，要你用不超过1000个点构建一张图，使得这张图中从1号点到n号点刚好有k条最短路。
想法很简单，乘法原理加加法原理就可以解决了。
我的想法就是下面这张图:
比如，上面这张图就是k=31=11111的图，我们把k化为2进制后，从左到右，先加
1—>3这条边，然后加3—>4,3—>5,4—>5,5—>6这四条边，就将总的方案数乘以了2，得到了2=10的图，再加上1—>6的这一条边，方案数+1，变为了3=11的方案数，继续将11左移，即加上6—>7,6—>8,7—>9，8—>9这四条边，方案数就变为了6=110，再+1得到7=111的图，以此类推。
所以，对于一个数k，我们从二进制的左边第一位开始向右找，每移动一位就加三个点，使方案数*2，若当前位上为1，则在下方加一条边从1连到当前的点，将方案数+1，否则不加，这样就构造出了整个图。
因为要保证最短路，所以下方的路径要与上方对应，如图所示的加一条边的方法是非常节约点的，但本人的代码因为是在考场上写的，因此多加了很多无用的点，最极端的数据会用到899个点，但如果像上图一样加边的话，最多60*5个点就够了，代码如下：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
using namespace std;
/*
101-->1011(加一条边)-->10110(*2)
*/
int cnt,ll,last,k;//last表示加倍时应连接的最后一个点,cnt为点的总数
int f[1000+10][1000+10];
void expand()//方案数加倍
{
f[last][cnt+1]=f[last][cnt+2]=1;
f[cnt+1][last]=f[cnt+2][last]=1;
cnt+=3;
f[cnt][cnt-1]=f[cnt][cnt-2]=1;
f[cnt-1][cnt]=f[cnt-2][cnt]=1;
ll+=2;
last=cnt;
}
void add()//新加一条边
{
int ret=cnt;
cnt+=ll;
cnt--;
int la=1;
for(int j=ret+1;j<=cnt;j++)
{
f[la][j]=f[j][la]=1;
la=j;
}
f[la][last]=f[last][la]=1;
}
int lowbit(int x)
{
return x&(-x);
}
void work()
{
int sum,tt=0;
int ret=k;
while(ret)
{
sum=lowbit(ret);
ret-=lowbit(ret);
}
//求第一个1
while(sum)
{
sum=(sum>>1);
tt++;
}
//初始化，有一条边，最后一个点是3
f[1][3]=1;
f[3][1]=1;
ll=1;
cnt=3;
last=3;
for(int i=tt-2;i>=0;i--)
{
expand();//左移一位
if((1<<i)&k)
{
add();//为1，加1条边
}
}
//最后一个点连上2
f[last][2]=1;
f[2][last]=1;
//输出
printf("%d\n",cnt);
for(int i=1;i<=cnt;i++)
{
for(int j=1;j<=cnt;j++)
{
if(f[i][j])
{
printf("Y");
}
else printf("N");
}
printf("\n");
}
}
int main()
{
scanf("%d",&k);
work();
return 0;
}
当然，Gemini同学用十进制也做出来了，还抢了一血，对其机智表示膜拜。
下来后还看到了一份神代码，只用了100个点，还是为了凑整，简直膜拜，代码如下(注释是本人加的)：
#include <stdio.h>
#include <string.h>
const int N = 105;
int g[N][N];
inline void set (int x, int y)
{
g[x][y] = g[y][x] = 1;
}
void init () //预处理出初始图
{
memset(g, 0, sizeof(g));
set(1, 3); set(1, 4); set(2, 100);
for (int i = 3; i < 60; i += 2) //交叉加边
{
set(i, i+2); set(i, i+3);
set(i+1, i+2); set(i+1, i+3);
}
for (int i = 63; i < 100; i++) set(i, i+1);//直线连边
}
void solve ()
{
int k;
scanf("%d", &k);
for (int i = 30; i; i--) if (k >= (1<<i)) //二进制加边
{
k -= (1<<i);
set(2*i+1, 63+i); set(2*i+2, 63+i);
}
if (k) set(1, 63);
}
void put () //输出地图
{
printf("100\n");
for (int i = 1; i <= 100; i++)
{
for (int j = 1; j <= 100; j++)
printf("%c", g[i][j] ? 'Y' : 'N');
printf("\n");
}
}
int main ()
{
init();
solve ();
put();
return 0;
}
代码很短，只有49行，运行速度超快。
什么意思呢，大概如下图：
他是先构建了一个这样的图，其中到3,4号点的路有1条，5,6有两条，61,62有2^29条路，这样的话，如果当前要加1的方案数，只需将1号点连到63号点，若要加2，则将3,4,一起连到64号点，以此类推。可以证明这些路的长度相等。因此，我们将k化为二进制，然后扫一遍，有1则加边，不然不管，就将图构建出来了。
只能膜拜了。