P1144 最短路计数题解
__vector__
·
·
个人记录
这是一个很lj的题解
难度：\color{green}\text{普及+/提高}
\color{green}\text{AC算法}：dijkstra
题目分析：
根据题目，让求的是从从顶点1到其他n-1个点的最短路有多少条。既然是要求最短路，肯定要用到dijkstra。然后开一个数组ans[maxn]来记录到第i个点有多少条最短路。在dijkstra中在更新最短距离时顺手更新ans[i]即可。
具体做法：
$dijkstra$更新最短距离时，如果发现$dis[to] > dis[u] + 1$，也就是说当前点$u \rightarrow to$不是最短距离，之前统计的到$to$的最短数($ans[to]$)肯定都要全部作废，也就是：
```cpp
ans[to] = ans[u];
```
如果是当前距离就是最短距离，那么直接加上从$u$转移过来的路径数($ans[u]$)即可，也就是：
```cpp
ans[to] += ans[u];
```
到此，本题就做完了，要记得取模。下面是代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
#define reg register
const int maxn=1e6+5;
const int maxm=4e6+5;
int n,m;
int dis[maxn];
int head[maxn];
int ans[maxn];
bool vis[maxn];
struct EDGE
{
int to,nxt;
}edge[maxm];
int tot;
inline void add(int u,int to)
{
edge[++tot].to=to;
edge[tot].nxt=head[u];
head[u]=tot;
}
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-')f=-1;
ch=getchar();
}
while(isdigit(ch))
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
inline void solve()
{
memset(dis,0x3f3f3f3f,sizeof(dis));
priority_queue< pair<int,int> > que;
que.push(make_pair(0,1));
dis[1]=0;
ans[1]=1;
reg int u;
while(!que.empty())
{
u=que.top().second;
que.pop();
if(vis[u])continue;
vis[u]=1;
reg int to;
for(reg int i=head[u];i;i=edge[i].nxt)
{
to=edge[i].to;
if(dis[to]>dis[u]+1)
{
dis[to]=dis[u]+1;
ans[to]=ans[u];
que.push(make_pair(-dis[to],to));
}
else if(dis[to]==dis[u]+1)
{
ans[to]+=ans[u];
ans[to]%=100003;
}
}
}
for(reg int i=1;i<=n;i++)
{
printf("%d\n",ans[i]);
}
}
int main()
{
n=read();
m=read();
reg int x,y;
for(reg int i=1;i<=m;i++)
{
x=read();
y=read();
add(x,y);
add(y,x);
}
solve();
return 0;
}
```