首页 > 代码库 > hdu 1688

hdu 1688

最短路与次短路条数

#include <stdio.h>#include <string.h>#define N 10005#define INF 0x3f3f3f3fstruct Edge{    int u,val,next;}e[2*N];int p[N],vis[N][2],d[N][2],cnt[N][2];void add(int n,int m){    int i,x,y,cost,cout = 1;    for(i = 1 ; i <= n ; i++) p[i] = -1;    while(m--)    {        scanf("%d %d %d",&x,&y,&cost);        e[cout].u = y;        e[cout].val = cost;        e[cout].next = p[x];        p[x] = cout++;    }}int dijkstra(int s,int t,int n,int m){    int i,x,y,temp,ok;    for(i = 1 ; i <= n ; i++)    {        d[i][0] = INF;        d[i][1] = INF;        vis[i][0] = 0;        vis[i][1] = 0;    }    d[s][0] = 0;    cnt[s][0] = 1;    for(i = 1 ; i <= 2*n ; i++)    {        temp = INF,ok ,x = -1;        for(y = 1 ; y <= n ;y++)            if(!vis[y][0]&&temp>d[y][0]) {                temp = d[y][0];                ok = 0;                x = y;            }        else if(!vis[y][1]&&temp>d[y][1]) {            temp = d[y][1];            ok = 1;            x = y;        }        if(x == -1) break;        vis[x][ok] = 1;        for(y = p[x] ; y!=-1; y = e[y].next)        {            int newd = d[x][ok]+e[y].val;            int u = e[y].u;            if(newd<d[u][0])            {                d[u][1] = d[u][0];                d[u][0] = newd;                cnt[u][1] = cnt[u][0];                cnt[u][0] = cnt[x][ok];            }else if(newd == d[u][0]){                cnt[u][0] += cnt[x][ok];            }else if(newd<d[u][1]){                d[u][1] = newd;                cnt[u][1] = cnt[x][ok];            }else if(newd == d[u][1]){                cnt[u][1]+=cnt[x][ok];            }        }    }    int num = cnt[t][0];    if(d[t][0] + 1 == d[t][1]) num+=cnt[t][1];    return num;}int main(){    int t,n,m;    scanf("%d",&t);    while(t--)    {        scanf("%d %d",&n,&m);        add(n,m);        int s,t;        scanf("%d %d",&s,&t);        int ans = dijkstra(s,t,n,m);        printf("%d\n",ans);    }    return 0;}