链接：

【题意】

      给出一个整数K，构造出刚好含有K条从1到2的最短路的图。

【分析】

      由于是要自己构造图，当然构造的方法很多了，需要考虑简单性和可行性。出于简单考虑，图中从1到2的所有路径都是最短路，为了保证路径长度一样，在构图时就需要分层次，使得每一层的点距离上一层的点的距离都是一个单位。

     那么如何使得路径条数刚好为K呢，这里涉及到相邻层次的点的链接方式。比如说每个点和上一层的所有点都有链接，那么这样总的路径数就是每层点的个数乘起来，但是这很难保证乘起来的值刚好是K，于是想到进制数的方法，可以构造出不同底数的链接模型，最后串联起来，起到相加作用，最后一定能凑成K。好需要注意的是点的个数，如果层次分的少了点的个数就多了，超过限制就错了。

     不过我在这里不用上面那种拼接方式，而是使用种更巧妙地构图，这种图有许多很好的性质，说不定有其它的用途，我就不用文字说明了，看图：

【代码】

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 using namespace std; 7 int cnt[100]; 8 long long dp[100]; 9 bool g[1001][1001];10 int k;11 int top;12 void addedge(int a,int b)13 {14     g[a][b]=g[b][a]=true;15 }16 void work(int c)17 {18     vector
           
             fin;19 int p=2,offset;20 while (p<=c)21 {22 int t=top;23 for (;top
            
             =0;--i)33 {34 int t=i-1;35 if (t<0) t=0;36 if ((1<
             
              <=k)37 {38 k-=(1<
              
               >=1;}61 work(c);62 }63 }