题解|大吉大利,晚上吃鸡!

大吉大利,晚上吃鸡!

http://www.nowcoder.com/questionTerminal/c40bcbb3d0344401bf3cfb812e5d2dfc

    因为这道题目要求的是方案数,所以我们设一个两维数组f[i][x]作为从s(i==0)/t(i==1)到点x的最短路的条数。于是条件1就被转化为了:

    求两个点A和B,使得f[0][A]*f[1][A]+f[0][B]*f[1][B]=f[0][T](或者f[1][S])

    为了求出f数组,我们需要正反各跑一遍dijkstra,然后建出一个从S到T的最短路的图(显然这个图是一个DAG)。于是我们就满足了条件1。

    对于条件2的满足也很简单,我们只需要判断在这个最短路的DAG上,点A能否走到点B就可以了。

#include<cstdio>
#include<queue>
#include<map>
#include<cstring>
#include<bitset>
using namespace std;
inline void read(int &x,char ch=getchar(),bool f=0)
{
    for(x=0;ch>'9'||ch<'0';f=ch=='-',ch=getchar());
    for(;ch>='0'&&ch<='9';x=(x<<3)+(x<<1)+(ch^48),ch=getchar());
    (f)&&(x=-x);
}
const int N=5e4+5,M=5e4+5,mod=1e9+7;
int n,m,s,t;

//Part 1:Dijkstra
bool vis[N];
int f[2][N];
int head[M],cnt;
long long dis[2][N];
struct edge{
int next,go,val;
}e[M<<1];
inline void add(int u,int v,int w){e[++cnt]=(edge){head[u],v,w},head[u]=cnt;}
struct data{
int u;
long long d;
bool operator <(const data&a)const
{
return d>a.d;
}
};
void dij(int s,int fx)
{
memset(dis[fx],0x3f,sizeof(dis[fx]));
dis[fx][s]=0,f[fx][s]=1;
memset(vis,0,sizeof(vis));
priority_queue<data> q;
q.push((data){s,0});
while(!q.empty())
{
data u=q.top();
q.pop();
if(vis[u.u])continue;
vis[u.u]=1;
for(int i=head[u.u];i;i=e[i].next)
{
int v=e[i].go;
if(dis[fx][v]>dis[fx][u.u]+e[i].val)
{
dis[fx][v]=u.d+e[i].val;
f[fx][v]=0;
q.push((data){v,dis[fx][v]});
}
if(dis[fx][v]==dis[fx][u.u]+e[i].val)//如果有多条最短路,就把方案数累加
f[fx][v]+=f[fx][u.u],f[fx][v]%=mod;//取模,不用管它
}
}
}

//Part 2:Topsort

//为了避免混淆,用namespace封***itset<N> from[N],to[N];
map<int,bitset<N> > uv;
int g[N];
namespace tp
{
    int head[N]={0},q[N]={0},in[N]={0},cnt=0;
    struct edge{
        int next,go;
    }e[M];
    inline void add(int u,int v){e[++cnt]=(edge){head[u],v},head[u]=cnt;}
    void topsort()//用拓扑处理出dp的顺序
    {
        for(int i=1,v;i<=cnt;i++)v=e[i].go,++in[v];
        int hea=0,tail=0;
        for(int i=1;i<=n;i++)
            if(in[i]==0)
                q[++tail]=i;
        while(tail<n)
        {
            int u=q[++hea];
            for(int i=head[u];i;i=e[i].next)
            {
                int v=e[i].go;
                --in[v];
                if(in[v]==0)q[++tail]=v;
            }
        }
    }
    long long solve()
    {
        long long ret=0;
        for(int i=1;i<=n;i++)//正向跑一遍
        {
            int uu=q[i];
            from[uu][uu]=1;
            for(int j=head[uu],vv;j;j=e[j].next)
            {
                vv=e[j].go;
                from[vv]|=from[uu];
            }
        }
        for(int i=n;i>=1;i--)//反向跑一遍
        {
            int uu=q[i];
            to[uu][uu]=1;
            for(int j=head[uu],vv;j;j=e[j].next)
            {
                vv=e[j].go;
                to[uu]|=to[vv];
            }
        }
        for(int i=1;i<=n;i++)//将答案累加
        {
            int uu=q[i];
            ret+=((~(from[uu]|to[uu]))&uv[(g[t]-g[uu]+mod)%mod]).count();
        }
        return ret>>1;//除2,避免重复
    }
}
int main()
{
    read(n),read(m),read(s),read(t);
    for(int i=1,u,v,w;i<=m;i++)
    {
        read(u),read(v),read(w);
        add(u,v,w),add(v,u,w);
    }
    dij(s,0);
    dij(t,1);
    if(f[0][t]==0)//注意判断不连通的情况(等价于f[1][s]==0)
    {
        printf("%lld",1ll*n*(n-1)>>1);//A可能情况*B可能情况/2(防止重复)
        return 0;
    }
    for(int i=1;i<=n;i++)
    {
        if(dis[0][i]+dis[1][i]==dis[0][t])//如果这个点在从S到T的最短路上,就把它的方案数存起来
            g[i]=1ll*f[0][i]*f[1][i],g[i]%=mod;
        uv[g[i]][i]=1;//map存储
    }
    for(int i=1;i<=cnt;i+=2)//对于每一条合法的边,在新的图中加一条边
    {
        int v1=e[i].go,v2=e[i+1].go;
        if(dis[0][v1]+dis[1][v2]+e[i].val==dis[0][t])tp::add(v1,v2);
        if(dis[0][v2]+dis[1][v1]+e[i].val==dis[0][t])tp::add(v2,v1);
    }
    tp::topsort();//因为是DAG,所以可以用拓扑
    long long ans=tp::solve();//ans存储dp答案
    printf("%lld",ans);
    return 0;
}

  


全部评论
f[fx][v]%=mod; 方案数取模不会被卡吗?
点赞 回复 分享
发布于 2022-10-19 15:43 江苏

相关推荐

挣K存W养DOG:他真的很中意你,为什么不回他
点赞 评论 收藏
分享
小灰呵呵呵:网签还是纸质三方啊
点赞 评论 收藏
分享
评论
9
收藏
分享
牛客网
牛客企业服务