次小生成树。求出两点间最短路径的最大权值，再把要加入的边与之比较即可。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 using namespace std; 6  7 const int MAXN=1010; 8 const int MAXM=100010; 9 const int inf=100000000;10 int map[MAXN][MAXN];11 int edge[MAXM][3];12 bool exist[MAXN][MAXN],used[MAXN][MAXN],vis[MAXN];13 int f[MAXN][MAXN],dist[MAXN],pre[MAXN]; 14 int m,n,q;15 int ans1=0;16 void init(){17     for(int i=1;i<=n;i++){18         vis[i]=false;19         for(int j=i;j<=n;j++){20             map[i][j]=map[j][i]=inf;21             exist[i][j]=exist[j][i]=used[i][j]=used[j][i]=false;22             f[i][j]=f[j][i]=0;23         }24     }25 }26 27 void prim(){28     dist[1]=0;29     for(int i=2;i<=n;i++){30         dist[i]=map[1][i];31         if(dist[i]!=inf)32         pre[i]=1;33         else pre[i]=-1;34     }35     vis[1]=true;36     for(int i=1;i<=n;i++){37         int min=inf,p=-1;38         for(int k=1;k<=n;k++){39             if(dist[k]