【最短路】HDU 1688 Sightseeing

题目大意

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

输入格式

第一行是数据组数(T)。
对于魅族数据，第一行是(n)和(m)，表示节点数和边数。
接下来(m)行，每行三个整数(a)，(b)，(l)，表示(a ightarrow b)有一条边，长度为(l)。
最后两个整数表示(S)和(F)。

输出格式

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

数据范围

(2le nle 1000，1le mle 10000，1le a,ble n，1le lle 1000，1le ansle 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
",ans);
    }
}