最短路和次短路的结合，之前没有碰到过次短路。为此自己特地把最短路知识又复习了一遍，然后看了其他人的想法，最后才写了出来，具体来说，其实不太难，重点是理解思想。存储的时候采用邻接表。

?

解法：

用到的数组：dist[i][0]:i到起点的最短路，dist[i][1]:i到起点的严格次短路

visited[i][0],visited[i][1]:同一维的visited数组，标记距离是否已确定

sum[i][0]:i到起点的最短路条数，sum[i][1]:i到起点的次短路条数

?

同一维dijkstra，内循环先找出最短的距离(次短路或最短路)d，然后枚举与该点相连的点：

if(d < 最小) 更新最小和次小，包括距离以及路径条数

else if(d == 最小) 更新最短路径条数

else if(d < 次小) 更新次小，包括次小距离路径条数

else if(d == 次小) 更新次小路径条数

?

从这题自己也学到了一点东西：

之前写最短路的题目时，总是在求最短路的距离，没有碰到求最短路有几条的。那么只有把这题稍微修改一下不就可以求解最短路径有几条了吗？而且再把这题的算法稍微修改一下不就可以求次短路了吗？

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         using namespace std; const int inf=1<<28; const int N=1005; const int M=10005;www.2cto.com int dist[N][2],sum[N][2],head[N]; bool visited[N][2]; struct Edge { int v,w; int next; }edge[M]; int top,s,e,n,m; void add_edge(int u,int v,int w) { edge[top].v=v,edge[top].w=w; edge[top].next=head[u]; head[u]=top++; } void solve() { memset(visited,false,sizeof(visited)); memset(sum,0,sizeof(sum)); for(int i=1;i<=n;i++) { dist[i][0]=inf; dist[i][1]=inf; } dist[s][0]=0; sum[s][0]=1; while(true) { int _min=inf,flag=-1,pos=-1; for(int i=1;i<=n;i++) { if(!visited[i][0]&&_min>dist[i][0]) _min=dist[i][0],pos=i,flag=0; else if(!visited[i][1]&&_min>dist[i][1]) _min=dist[i][1],pos=i,flag=1; } if(pos==-1) break; visited[pos][flag]=true; for(int i=head[pos];i!=-1;i=edge[i].next) { int v=edge[i].v,w=edge[i].w; int temp=dist[pos][flag]+w; if(temp