图论专题训练1-C(最短路和次短路问题,dijkstra算法)

/* 
 *题目大意： 
 *在一个有向图中,求从s到t两个点之间的最短路和比最短路长1的次短路的条数之和; 
 * 
 *算法思想： 
 *用A*求第K短路,目测会超时,直接在dijkstra算法上求次短路; 
 *将dist数组开成二维的,即dist[v][2],第二维分别用于记录最短路和次短路; 
 *再用一个cnt二维数组分别记录最短路和次短路的条数; 
 *每次更新路径的条数时,不能直接加1,,应该加上cnt[u][k],k为次短路径或者最短路径的标记; 
 *图有重边,不能用邻接矩阵存储; 
 *不知道为什么,题目上说的是N and M, separated by a single space, with 2≤N≤1000 and 1 ≤ M ≤ 10000; 
 *而我的代码硬是把N开成1W了才过,求解释,RE了无数次,擦; 
**/  
#include  
#include  
#include  
#include  
#include  
using namespace std;  
  
const int N=11111;  
const int M=111111;  
const int INF=0xffffff;  
  
struct node  
{  
    int to;  
    int w;  
    int next;  
};  
  
node edge[N];  
int head[N];  
  
int dist[N][2],cnt[N][2];  
bool vis[N][2];  
int n,m,s,t,edges;  
  
void addedge(int u,int v,int w)  
{  
    edge[edges].w=w;  
    edge[edges].to=v;  
    edge[edges].next=head[u];  
    head[u]=edges++;  
}  
  
int dijkstra()  
{  
    int k;  
    for(int i=0; i<=n; i++)  
    {  
        dist[i][0]=dist[i][1]=INF;  
        vis[i][0]=vis[i][1]=0;  
        cnt[i][0]=cnt[i][1]=0;  
    }  
    cnt[s][0]=1,dist[s][0]=0;  
  
    for(int i=1; i<=n*2; i++)  
    {  
        int u=-1;  
        int min_dist=INF;  
        for(int j=1; j<=n; j++)  
            for(int flag=0; flag<2; flag++)  
                if(!vis[j][flag]&&dist[j][flag]