首页 > 代码库 > spfa+dp(洛谷1144 最短路计数)
spfa+dp(洛谷1144 最短路计数)
给出一个N个顶点M条边的无向无权图，顶点编号为1～N。问从顶点1开始，到其他每个点的最短路有几条。
输入格式：
输入第一行包含2个正整数N，M，为图的顶点数与边数。
接下来M行，每行两个正整数x, y，表示有一条顶点x连向顶点y的边，请注意可能有自环与重边。
输出格式：
输出包括N行，每行一个非负整数，第i行输出从顶点1到顶点i有多少条不同的最短路，由于答案有可能会很大，你只需要输出mod 100003后的结果即可。如果无法到达顶点i则输出0。
输入样例#1：
5 71 21 32 43 42 34 54 5
输出样例#1：
11124
讲一下思路吧，跑一遍spfa，由于每条边的权值为1，所以第一次遍历到的点的权值肯定是最小的。然后运用dp的思想，每次遍历到的点的方案数等于前面的方案数之和，于是数组开大点就能a了。原谅我写dp是看题解大神的~
这次我的代码应该比较清晰~
#include<bits/stdc++.h>#define maxn 3000000#define maxm 3000000#define inf 129302101 using namespace std;struct Edge{ int to,next,w;};int n,m;struct Edge edge[maxm];int head[maxn],book[maxn],dis[maxn];int dp[maxn];int cnt=0;void add(int u,int v,int w){ edge[++cnt].to=v; edge[cnt].next=head[u]; edge[cnt].w=w; head[u]=cnt;}void spfa(){ queue<int> q; memset(book,0,sizeof(book)); q.push(1); for(int i=1;i<=m;i++) dis[i]=inf; dis[1]=1; dp[1]=1; book[1]=1; int ans=0; while(!q.empty()) { int j=q.front();q.pop(); for(int i=head[j];i;i=edge[i].next) { int v=edge[i].to; if(!book[v]) { book[v]=1; dis[v]=min(dis[v],dis[j]+1); dp[v]+=dp[j]%100003; q.push(v); } else if(dis[v]==dis[j]+1) dp[v]+=dp[j]%100003; } }}int main(){ cin>>n>>m; int u,v; for(int i=1;i<=m;i++) { cin>>u>>v; add(u,v,1); add(v,u,1); } spfa(); for(int i=1;i<=n;i++) cout<<dp[i]%100003<<endl; return 0;}
spfa+dp(洛谷1144 最短路计数)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。