不是最优解法,写着练手的,没数据测,不知道还有没有边界问题,仅供参考
可以有负权边,不能有负环,比如负的双向边
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define x first
#define y second
using namespace std;
const int N = 1e5 + 10, M = 8e5 + 10, mod = 100003;
typedef pair<int, int> PII;
int n, m;
int h[N], sh[N], e[M], ne[M], idx;
int q[N], dist[N], cnt[N], in[N];
bool st[N];
void add(int *h, int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void spfa()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
int hh = 0, tt = 0;
q[tt ++] = 1;
while (hh != tt)
{
int t = q[hh ++];
if (hh == N) hh = 0;
st[t] = false;
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + 1)
{
dist[j] = dist[t] + 1;
if (!st[j])
{
q[tt ++] = j;
if (tt == N) tt = 0;
st[j] = true;
}
}
}
}
}
void build()
{
memset(sh, -1, sizeof sh);
for (int i = 1; i <= n; i ++)
for (int j = h[i]; ~j; j = ne[j])
{
int k = e[j];
if (dist[k] == dist[i] + 1)
{
in[k] ++;
add(sh, i, k);
}
}
}
void top_sort()
{
int hh = 0, tt = -1;
q[++ tt] = 1;
cnt[1] = 1;
while(hh <= tt)
{
auto t = q[hh ++];
for (int i = sh[t]; ~i; i = ne[i])
{
int j = e[i];
cnt[j] = (cnt[j] + cnt[t]) % mod;
in[j] --;
if (in[j] == 0) q[++ tt] = j;
}
}
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
while (m -- )
{
int a, b;
cin >> a >> b;
add(h, a, b), add(h, b, a);
}
spfa();
build();
top_sort();
for (int i = 1; i <= n; i ++)
cout << cnt[i] << endl;
return 0;
}
神牛