这道题的大致意思是给你一个有20个点的无向图，再给你最多100个查询。让你每次查询输出两个顶点之间的最短路径长度。

本题是最基础的图论题，解决方法有多种，下面我们列举若干种方法并结合其效率进行讨论:

一、简单BFS

这种算法是最基本的算法，对于任意两个点直接用广度优先搜索惊醒最短路径求解。写起来方便但是效率并不怎么高。

代码如下：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              
               10 #define LEN 3011 using namespace std;12 13 int Map[LEN][LEN], vis[LEN], cnt = 1;14 15 typedef struct{16 int v, step;17 }P;18 19 int BFS(int st, int end)20 {21 queue
               
 q;22 P ss;23 ss.v = st;24 ss.step = 0;25 vis[st] = 1;26 q.push(ss);27 while(!q.empty()){28 P vex = q.front();29 q.pop();30 if(vex.v==end){31 return vex.step;32 }33 for(int i=1; i<22; i++){34 P newv;35 newv.v = i;36 newv.step = vex.step+1;37 if(Map[vex.v][i]==1 && vis[i]==0){38 vis[i] = 1;39 q.push(newv);40 }41 }42 }43 return -1;44 }45 46 int main()47 {48 // freopen("in.txt", "r", stdin);49 50 int vex, n;51 while(scanf("%d", &n)!=EOF){52 //building Map53 memset(Map, 0, sizeof Map);54 for(int i=0; i
              
             
            
           
          
         
        
       
      

二、简单BFS+记忆化

上一种算法只要稍稍改进一下即可在时间效率上有不错的提升，首先我们从搜索过程中考虑在广度优先搜索中我们再求到最小值之前其实经过了很多节点，我们每到一个结点其实已经求出了起始点到他的最短路径。若是用一张表记录下来我们下次就可以不重复求解。这次程序中dis数组就起到了这个作用。若询问时dis[a][b]==-1则说明在以前没有求解过，需调用BFS。否则直接输出相应表项即可。

代码如下：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              
               10 #define LEN 3011 12 using namespace std;13 14 int Map[LEN][LEN], vis[LEN], cnt = 1;15 int dis[LEN][LEN];16 17 typedef struct{18 int v, step;19 }P;20 21 int BFS(int st, int end)22 {23 queue
               
 q;24 P ss;25 ss.v = st;26 ss.step = 0;27 vis[st] = 1;28 q.push(ss);29 while(!q.empty()){30 P vex = q.front();31 q.pop();32 if(dis[st][vex.v]==-1)dis[st][vex.v] = vex.step; //做记录33 if(vex.v==end){34 return vex.step;35 }36 for(int i=1; i<22; i++){37 P newv;38 newv.v = i;39 newv.step = vex.step+1;40 if(Map[vex.v][i]==1 && vis[i]==0){41 vis[i] = 1;42 q.push(newv);43 }44 }45 }46 return -1;47 }48 49 int main()50 {51 // freopen("in.txt", "r", stdin);52 53 int vex, n;54 while(scanf("%d", &n)!=EOF){55 //building Map56 memset(Map, 0, sizeof Map);57 memset(dis, -1, sizeof dis);58 for(int i=0; i<22; i++) dis[i][i] = 0;59 for(int i=0; i
              
             
            
           
          
         
        
       
      

三、dijkstra算法

本题边的权值均为1，用dij算法是大材小用了，但是从时间上看是n^3与前一算法大致一样。我用了n次dij就把任意两点之间的距离都求了出来最后只需查询dis数组即可得到答案。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              
               10 #define LEN 3011 #define INF 0x7fffffff12 using namespace std;13 14 int Map[LEN][LEN], dis[LEN][LEN], vis[LEN], cnt = 1;15 16 void init()17 {18 for(int i=0; i<=20; i++){19 for(int j=0; j<=20; j++)20 Map[i][j] = INF;21 Map[i][i] = 0;22 }23 memset(dis, 0, sizeof dis);24 }25 26 void Dijkstra(int vex)27 {28 memset(vis, 0, sizeof vis);29 for(int i=1; i<=20; i++)30 dis[vex][i] = Map[vex][i];31 vis[vex] = 1;32 for(int i=1; i<20 ;i++)33 {34 int min, mindis = INF;35 for(int j=1; j<=20; j++)36 if(dis[vex][j]
              
             
            
           
          
         
        
       
      

四、dijkstra算法+IO优化

第一次写IO优化表示只是读取正整数还是比较简单的。

代码如下：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              
               10 #define LEN 3011 #define INF 0x7fffffff12 using namespace std;13 14 int Map[LEN][LEN], dis[LEN][LEN], vis[LEN], cnt = 1;15 16 void init()17 {18 for(int i=0; i<=20; i++){19 for(int j=0; j<=20; j++)20 Map[i][j] = INF;21 Map[i][i] = 0;22 }23 memset(dis, 0, sizeof dis);24 }25 26 void Dijkstra(int vex)27 {28 memset(vis, 0, sizeof vis);29 for(int i=1; i<=20; i++)30 dis[vex][i] = Map[vex][i];31 vis[vex] = 1;32 for(int i=1; i<20 ;i++)33 {34 int min, mindis = INF;35 for(int j=1; j<=20; j++)36 if(dis[vex][j]
               
                '9');53 ret = 0;54 while(c>='0' && c<='9'){55 ret = ret*10+(c-'0');56 c = getchar();57 }58 }59 60 int main()61 {62 // freopen("in.txt", "r", stdin);63 64 int vex, n;65 while(scanf("%d", &n)!=EOF){66 //building Map67 init();68 for(int i=0; i
               
              
             
            
           
          
         
        
       
      

五、dijkstra算法+优先队列优化+IO优化

无聊的时候有换了O（mlogn）的Dij重写了一遍时间稳定在0.07左右，又快了一些。

代码如下：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              
               10 #include 
               
                11 #include 
                
                 12 #define LEN 3013 #define INF 0x7fffffff14 using namespace std;15 16 int dis[LEN][LEN], vis[LEN], cnt = 1;17 vector
                 
                   Map[LEN];18 typedef pair
                  
                    pii;19 20 void init()21 {22 for(int i=0; i
                   
                    , greater
                    
                      > q;30 for(int i=0; i<21; i++)dis[vex][i] = (i==vex?0:INF);31 memset(vis, 0, sizeof vis);32 q.push(make_pair(dis[vex][vex], vex));33 while(!q.empty()){34 pii u = q.top(); q.pop();35 int x = u.second;36 if(vis[x]) continue;37 vis[x] = 1;38 for(vector
                     
                      ::iterator it = Map[x].begin(); it!=Map[x].end(); ++it){39 if(dis[vex][*it]>dis[vex][x]+1) {40 dis[vex][*it] = dis[vex][x]+1;41 q.push(make_pair(dis[vex][*it], *it));42 }43 }44 }45 }46 47 inline void read(int &ret)48 {49 char c;50 while((c = getchar())<'0' || c>'9');51 ret = 0;52 while(c>='0' && c<='9'){53 ret = ret*10+(c-'0');54 c = getchar();55 }56 }57 58 int main()59 {60 // freopen("in.txt", "r", stdin);61 62 int vex, n;63 while(scanf("%d", &n)!=EOF){64 //building Map65 init();66 for(int i=0; i