【最短路】HDU 1688 Sightseeing

题目大意

给出一个有向图（可能存在重边），求从\(S\)到\(F\)最短路的条数，如果次短路的长度仅比最短路的长度多1，那么再加上次短路的条数。

输入格式

第一行是数据组数\(T\)。

对于魅族数据，第一行是\(n\)和\(m\)，表示节点数和边数。

接下来\(m\)行，每行三个整数\(a\)，\(b\)，\(l\)，表示\(a\rightarrow b\)有一条边，长度为\(l\)。

最后两个整数表示\(S\)和\(F\)。

输出格式

对于每组数据输出一个答案\(ans\)。

数据范围

\(2\le n\le 1000，1\le m\le 10000，1\le a,b\le n，1\le l\le 1000，1\le ans\le 10^9\)

样例

2

5 8

1 2 3

1 3 2

1 4 5

2 3 1

2 5 3

3 4 2

3 5 4

4 5 3

1 5

5 6

2 3 1

3 2 1

3 1 10

4 5 2

5 2 7

5 2 7

4 13

样例输出

3

2

思路

用Dijkstra更新时分四种情况：

新路径比最短路径长度要小，最短路和次短路的长度和次数都要更新。
新路径等于最短路的长度，更新最短路的条数。
新路径比最短路要长但是比次短路要短，更新次短路的长度和条数。
新路径等于次短路径的长度，更新次短路径的条数。

代码

#include<stdio.h>

#include<string.h>

const int maxn=1010;

const int maxm=10010;

const int INF=0x3f3f3f3f;

int g[maxn][maxn],dis[maxn][2],cnt[maxn][2];

bool vis[maxn][2];

int n,m;

struct Edge{

    int v,w,to;

} edge[maxm];

int num,head[maxn];

void add(int u,int v,int w){

    edge[num].v=v;

    edge[num].w=w;

    edge[num].to=head[u];

    head[u]=num++;

}

void dij(int s){

    int now,min,k;

    for(int i=1; i<=n; i++){

        dis[i][0]=INF;

        dis[i][1]=INF;

    }

    memset(vis,false,sizeof(vis));

    cnt[s][0]=1;

    dis[s][0]=0;

    for(int i=1; i<2*n; i++){

        now=-1;

        min=INF;

        for(int j=1; j<=n; j++)

            if(!vis[j][0]&&min>dis[j][0]){

                k=0;

                min=dis[j][0];

                now=j;

            }

            else if(!vis[j][1]&&min>dis[j][1]){

                k=1;

                min=dis[j][1];

                now=j;

            }

        if(now==-1)break;

        vis[now][k]=1;

        for(int j=head[now]; j!=-1; j=edge[j].to){

            int v=edge[j].v;

            int len=dis[now][k]+edge[j].w;

            if(len<dis[v][0]){

                dis[v][1]=dis[v][0];

                cnt[v][1]=cnt[v][0];

                dis[v][0]=len;

                cnt[v][0]=cnt[now][k];

            }else if(len==dis[v][0]){

                cnt[v][0]+=cnt[now][k];

            }else if(len<dis[v][1]){

                dis[v][1]=len;

                cnt[v][1]=cnt[now][k];

            }else if(len==dis[v][1])

                cnt[v][1]+=cnt[now][k];

        }

    }

}

int main(){

    int T;

    scanf("%d",&T);

    while(T--){

        num=0;

        memset(head,-1,sizeof(head));

        scanf("%d%d",&n,&m);

        int a,b,c,s,f;

        for(int i=1; i<=m; i++){

            scanf("%d%d%d",&a,&b,&c);

            add(a,b,c);

        }

        scanf("%d%d",&s,&f);

        dij(s);

        int ans=cnt[f][0];

        if(dis[f][1]==dis[f][0]+1)

            ans+=cnt[f][1];

        printf("%d\n",ans);

    }

}

巴特西