P1144最短路计数·BFS/dijkstra

题解

其实题目很简单不写了，这里总结一下从这道题目里学到的知识：

1. 当最短路的边权都是1时，dijkstra/spfa 就是 BFS


2. 如果使用优先队列，内部结构是pair时，dis[v]=dis[u]+1使得当前路成为新的最短路，这条路在优先队列里的级别变高，应该使用q.push(make_pair{-dis[v],v})，有负号哦！

BFS版：

dijkstra版：

#include
using namespace std;
typedef pair<int,int> pii;
const int INF=0x3f3f3f3f;
const int mod=100003;
const int N=1e6+10;
vector<int>g[N];
int vis[N],dis[N];
int ans[N];
int n,m;
priority_queue< pii >q;
void dijkstra(){memset(dis, INF, sizeof dis);dis[1]=0;ans[1]=1;q.push({0,1});while(q.size()){int u=q.top().second;q.pop();if(vis[u])continue;vis[u]=1;for (int i = 0; i <g[u].size(); i++) {int v=g[u][i];if(dis[v]>dis[u]+1){dis[v]=dis[u]+1;ans[v]=ans[u];q.push({-dis[v],v});//更新之后的点是新的最短路 优先级别变高 应该跑到队列最前方 用-dis[v]控制//dis[v]的值是没有变 仍然是正的}else if( dis[v]==dis[u]+1){ans[v]=(ans[v]+ans[u])%mod;}}}
}
int main()
{cin>>n>>m;for (int i = 1,u,v; i <= m; i++) {cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}dijkstra();for (int i = 1; i <=n ; i++) {cout<<ans[i]<<endl;}return 0;
}