最短路计数
作者:
殇ベ_11
,
2021-02-03 15:42:50
,
所有人可见
,
阅读 300
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N = 444404;
const int maxn = 0x7fffffff;
int n,m,x,y;
struct edge{
int dis;
int next;
int to;
}e[N << 1];
int head[N],dis[N << 1];
int ans[N << 1];
int cnt;
inline void add(int u,int v,int d)
{
cnt++;
e[cnt].dis = d;
e[cnt].to = v;
e[cnt].next = head[u];
head[u] = cnt;
}
bool vis[N];
queue < int > q;
int u,v;
inline void spfa(int x)
{
for(int i=1;i<=n;i++)
dis[i] = maxn;
q.push(x);
vis[x] = 1;
ans[x] = 1;
dis[x] = 0;
while(!q.empty())
{
u = q.front();
q.pop();
for(int i = head[u]; i; i = e[i].next)
{
v = e[i].to;
if(dis[v] > dis[u] + e[i].dis)
{
dis[v] = dis[u] + e[i].dis;
ans[v] = ans[u];
if(!vis[v]){
vis[v] = 1;
q.push(v);
}
}
else if(dis[v] == dis[u] + e[i].dis)
{
ans[v] = (ans[v] + ans[u]) % 100003;
}
}
vis[u] = 0;
}
}
inline int read()
{
char c = getchar();
int f = 1;
int x = 0;
while(c < '0' || c > '9')
{
if(c == '-')
{
f = -1;
}
c = getchar();
}
while(c >= '0' &&c <='9')
{
x = (x << 1) + (x << 3) + (c - 48);
c = getchar();
}
return x * f;
}
int main()
{
n = read();
m = read();
while(m--)
{
x = read();
y = read();
add(x,y,1);
add(y,x,1);
}
spfa(1);
for(int i=1;i<=n;i++)
printf("%d\n",ans[i]);
}