题解 P1144 【最短路计数】
一道spfa的水题
-用spfa求最短路。。
-记录有多少个相同的到该点的最短路。。
-忽略重边。。
#include"stdafx.h"
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 0x7fffffff; // 0x3f不够。。。
int n, m, x, y;
int vis[1000010],dis[1000010], ans[1000010]; //ans存最短路个数
vector<int> g[1000010];
queue<int> q;
inline void spfa(int x)
{
for(int i=1; i<=n; i++)dis[i] = maxn;
q.push(x);
vis[x] = 1;
ans[x] = 1; // 本身为1个最短路
dis[x] = 0;
while (!q.empty())
{
u = q.front();
q.pop();
for (int i = 0; i < g[u].size(); i++)
{
v = g[u][i];
if (dis[v] > dis[u] + 1) //如果满足u到v的距离比原本到v的距离小，则更新
{
dis[v] = dis[u] + 1;
ans[v] = ans[u]; // v点和u点在一条路上，所以v的最短路个数等于u的最短路个数
if (!vis[v])
vis[v] = 1, q.push(v);
}
else if (dis[v] == dis[u] + 1)
ans[v] = (ans[v] + ans[u]) % 100003; // 该点最短路个数为u最短路个数+v最短路个数
}
vis[u] = 0;
}
}
int main()
{
cin >> n >> m;
while (m--)
{
cin >> x >> y;
g[x].push_back(y),g[y].push_back(x);
}
spfa(1);
for (int i = 1; i <= n; i++)
cout << ans[i] << endl;
return 0;
}