POJ - 3463 Sightseeing 最短路计数+次短路计数

F - Sightseeing

传送门： POJ - 3463

分析

一句话题意：给你一个有向图，可能有重边，让你求从s到t最短路的条数，如果次短路的长度比最短路的长度多1，那么在加上次短路的条数。

这道题唯一要注意的就是次短路的求法

首先题目中说从起点到终点至少有一条路径，所以我们就不用考虑不可达的情况

我们先考虑如果a到b有一条边，b到c有一条边

那么a到c经过b的路程中次短路只有两种选择，一种是a到b的最短路+b到c的次短路，另一种是a到b的次短路+b到c的次短路

所以我们只需要记录次短路和最短路两个值就可以了

然后我们去跑dij，每次加上一条边会有四种情况对答案产生影响

1.比最短路短

如果之前的最短路不为无穷大的话，我们就把原先最短路的值赋值给原先次短路的值，同时把次短路的数量更新为原先最短路的数量

再更新最短路，同时要把最短路的数量改为到达上一个节点的方案数

2.和最短路一样短

把最短路的数量加一

3.比次短路短

更新次短路的长度，同时要把次短路的数量改为到达上一个节点的方案数

4.和次短路一样长

把次短路的数量加一

代码

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

const int maxd=1005,maxb=20005;

int head[maxd],tot=1;

struct asd{

    int from,to,next,val;

}b[maxb];

void ad(int aa,int bb,int cc){

    b[tot].from=aa;

    b[tot].to=bb;

    b[tot].val=cc;

    b[tot].next=head[aa];

    head[aa]=tot++;

}

struct jie{

    int num,dis,jud;

    jie(int aa=0,int bb=0,int cc=0){

        num=aa,dis=bb,jud=cc;

    }

    bool operator < (const jie& A) const{

        return dis>A.dis;

    }

};

priority_queue<jie> q;

int dis[maxd][3],cnt[maxd][3];

bool vis[maxd][3];

void dij(int xx){

    memset(dis,0x3f,sizeof(dis));

    memset(cnt,0,sizeof(cnt));

    memset(vis,0,sizeof(vis));

    dis[xx][0]=0,cnt[xx][0]=1;

    q.push(jie(xx,0,0));

    while(!q.empty()){

        int now=q.top().num;

        int judd=q.top().jud;

        q.pop();

        if(vis[now][judd]) continue;

        vis[now][judd]=1;

        for(int i=head[now];i!=-1;i=b[i].next){

            int u=b[i].to;

            int ndis=dis[now][judd]+b[i].val;

            if(ndis<dis[u][0]){

                if(dis[u][0]!=0x3f3f3f3f){

                    dis[u][1]=dis[u][0];

                    cnt[u][1]=cnt[u][0];

                    q.push(jie(u,dis[u][0],1));

                }

                dis[u][0]=ndis;

                cnt[u][0]=cnt[now][judd];

                q.push(jie(u,ndis,0));

            }

            else if(ndis==dis[u][0]){

                cnt[u][0]+=cnt[now][judd];

            }

            else if(ndis==dis[u][1]){

                cnt[u][1]+=cnt[now][judd];

            }

            else if(ndis<dis[u][1]){

                dis[u][1]=ndis;

                cnt[u][1]=cnt[now][judd];

                q.push(jie(u,ndis,1));

            }

        }

    }

}

int main(){

    int t;

    scanf("%d",&t);

    while(t--){

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

        memset(&b,0,sizeof(struct asd));

        tot=1;

        int n,m;

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

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

            int aa,bb,cc;

            scanf("%d%d%d",&aa,&bb,&cc);

            ad(aa,bb,cc);

        }

        int qd,zd;

        scanf("%d%d",&qd,&zd);

        dij(qd);

        int ans=cnt[zd][0];

        if(dis[zd][0]==dis[zd][1]-1) ans+=cnt[zd][1];

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

    }

    return 0;

}

巴特西

POJ - 3463 Sightseeing 最短路计数+次短路计数

F - Sightseeing

分析

代码

最新文章

热门文章