luogu 1608 路径统计--最短路计数

https://www.luogu.org/problemnew/show/P1608

题意https://www.cnblogs.com/rmy020718/p/9440588.html相似，建议还没做的先去做一下。

当你看完上一题，就已经对最短路计数大体有一个思想了，但是本题中没有说不保证没有重边和自环，那么开一个map数组记录一下就好了，自环的话我使用spfa解决的，那么我们就可以按部就班的写最短路计数了。

不过有个bug源自于spfa算法，见下图。

当你按spfa的手动模拟的时候你会发现到达5号点的路径有3条，但是其真实路径只有两条，我们应该在处理完每一个点后将这个点的路径数量清零(在其更新完其他点以后)，避免二次计算的时候再次累加。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<queue>

using namespace std;

int i,j,m,n;

int head[];

int us[];

int t[];

int dis[];

int a[][];

queue<int>q;

int r()

{

    int aans=;

    char ch=getchar();

    while(ch<''||ch>'')

    ch=getchar();

    while(ch>=''&&ch<='')

    {

        aans*=;

        aans+=ch-'';

        ch=getchar();

    }

    return aans;

}

int spfa(int x)

{

    q.push(x);dis[x]=;t[x]=;

    while(!q.empty())

    {

        int x=q.front();

        q.pop();

        us[x]=;

        if(x==n)

        continue;

        for(i=;i<=n;i++)

        {

            if(dis[x]+a[x][i]==dis[i])

            t[i]+=t[x];

            if(dis[x]+a[x][i]<dis[i])

            {

                dis[i]=dis[x]+a[x][i];

                t[i]=t[x];

            }

        if(t[i]&&!us[i])

        us[i]=,q.push(i);

        }

        t[x]=;

    }

}

int main()

{

    n=r(),m=r();

    int x,y,z;

    memset(a,,sizeof(a));

    memset(dis,,sizeof(dis));

    for(i=;i<=m;i++)

    {

        x=r(),y=r(),z=r();

        if(a[x][y])a[x][y]=min(z,a[x][y]);

        else a[x][y]=z;

    }

    spfa();

    if(dis[n]!=a[][])cout<<dis[n]<<" "<<t[n]<<endl;

    else cout<<"No answer"<<endl;

    return ;

}

巴特西

luogu 1608 路径统计--最短路计数

最新文章

热门文章