M_sea

洛谷1144 最短路计数
Luogu算法类似于SPFA的Bfs。首先将$1$入队,然后扩展出一颗解答树。这颗树上每个节点的前驱节点就是节点$...
扫描右侧二维码阅读全文
16
2018/07

洛谷1144 最短路计数

Luogu

算法

类似于SPFA的Bfs。

首先将$1$入队,然后扩展出一颗解答树。

这颗树上每个节点的前驱节点就是节点$1$到这个节点的最短路的必经之路。

那么一边Bfs一边统计答案即可。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

struct Edge {
    int v,nxt;
    Edge() { this->v=this->nxt=0; }
};
Edge e[2000010];
int head[1000010],cnt=0;

inline void addEdge(int u,int v) {
    e[++cnt].v=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}

int n,m;
bool vis[1000010];
int ans[1000010],dep[1000010];
queue<int> Q;

inline void Bfs() {
    vis[1]=1,ans[1]=1,dep[1]=0;
    Q.push(1);
    while (!Q.empty()) {
        int u=Q.front(); Q.pop();
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v;
            if (!vis[v]) { vis[v]=1; dep[v]=dep[u]+1; Q.push(v); }
            if (dep[v]==dep[u]+1) ans[v]=(ans[v]+ans[u])%100003;
        }
    }
}

int main() {
    n=read(),m=read();
    for (re int i=1;i<=m;i++) {
        re int x=read(),y=read();
        addEdge(x,y);
        addEdge(y,x);
    }
    Bfs();
    for (re int i=1;i<=n;i++) printf("%d\n",ans[i]);
    return 0;
}
最后修改:2019 年 05 月 26 日 02 : 30 PM

发表评论