最短路
2026-09-12 07:53:44
发布于：浙江
16阅读
0回复
0点赞
豆包给的题。
注意到是无向无权图，所以直接跑 bfs 求最短路，但是我们要统计最短路数量，所以要再搞个 数组来记录每个点的最短路数量，如果可以更新最短路，那么我们一样也可以更新这个点的 值，因为最短路只有现在一个点能到，所以直接把 值照搬就行，如果一个点 走一步到 刚好与它原本的最短路距离一样，那么我们需要把 与 相加并取模，因为我们又有了一些最短路的走法。（从 过去的那些）
const int mod=100003;
const int maxn=1e6+5;
vector<int> g[maxn];
int n, m, dis[maxn], cnt[maxn];
int main()
{
cin>>n>>m;
for(int i = 1;i<=m;i++)
{
int x, y;
cin>>x>>y;
g[x].push_back(y);
g[y].push_back(x);
}
memset(dis,0x3f,sizeof dis);
queue<int> q;
dis[1]=0;
cnt[1]=1;
q.push(1);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int v:g[u])
{
if(dis[u]+1<dis[v])
{
dis[v]=dis[u]+1;
cnt[v]=cnt[u];
q.push(v);
}
else if(dis[u]+1==dis[v])
{
cnt[v]=(cnt[v]+cnt[u])%mod;
}
}
}
for(int i = 1;i<=n;i++) cout<<cnt[i]<<'\n';
}
有帮助，赞一个