LibreOJ10077. 「一本通 3.2 练习 3」最短路计数【最短路+DP】

10077. 「一本通 3.2 练习 3」最短路计数

【题目描述】

传送门

【题解】

这题我们知道如何判断这条边是不是最短路上的边,那么就可以DP求解了。但是要注意顺序,我们可以预处理出最短路路径(x,y),然后BFS走DP就可以了。

代码如下

#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
const int MAXN=1e5+5,MAXM=2e5+5,MOD=100003;
int n,m,Ans,dst[MAXN],F[MAXN],hd,tl,que[MAXN];
bool vis[MAXN];
struct xcw{
    int x,id;
    bool operator <(const xcw b)const{return x>b.x;}
};
priority_queue<xcw> hep;
struct Edge{
    int tot,lnk[MAXN],son[MAXM<<1],nxt[MAXM<<1];
    void Add(int x,int y){son[++tot]=y,nxt[tot]=lnk[x],lnk[x]=tot;}
}E,S;
int read(){
    int ret=0;char ch=getchar();bool f=1;
    for(;!isdigit(ch);ch=getchar()) f^=!(ch^'-');
    for(; isdigit(ch);ch=getchar()) ret=(ret<<1)+(ret<<3)+ch-48;
    return f?ret:-ret;
}
void DIJ(){
    memset(dst,63,sizeof(dst));dst[1]=0;
    hep.push((xcw){0,1});
    while(!hep.empty()){
        int MIN=hep.top().x,k=hep.top().id;hep.pop();
        if(vis[k]) continue;vis[k]=1;
        for(int j=E.lnk[k];j;j=E.nxt[j])
        if(dst[E.son[j]]>MIN+1) S.Add(k,E.son[j]),hep.push((xcw){(dst[E.son[j]]=MIN+1),E.son[j]});
    }
}
void MO(int &x){if(x>=MOD) x-=MOD;}
void BFS(){
    vis[que[hd=0,tl=1]=1]=1;
    while(hd^tl){
        int x=que[++hd];
        for(int j=E.lnk[x];j;j=E.nxt[j]) if(dst[x]==dst[E.son[j]]+1) MO(F[x]+=F[E.son[j]]);
        for(int j=S.lnk[x];j;j=S.nxt[j]) que[++tl]=S.son[j];
    }
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("prob.in","r",stdin);
    freopen("prob.out","w",stdout);
    #endif
    n=read(),m=read();
    for(int i=1,x,y,w;i<=m;i++) x=read(),y=read(),E.Add(x,y),E.Add(y,x);
    DIJ();F[1]=1;BFS();
    for(int i=1;i<=n;i++) printf("%d\n",F[i]);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部