洛谷1144 最短路计数

SPFA统计最短路数量

阅读全文大概需要 3分钟
本文总阅读量
Posted by yjjr's blog on October 13, 2018

标签:SPFA

题目

题目传送门

题目描述

给出一个\(N\)个顶点\(M\)条边的无向无权图,顶点编号为\(1-N\)。问从顶点\(1\)开始,到其他每个点的最短路有几条。

输入输出格式

输入格式

第一行包含\(2\)个正整数\(N,M\),为图的顶点数与边数。

接下来\(M\)行,每行\(2\)个正整数\(x,y\),表示有一条顶点\(x\)连向顶点\(y\)的边,请注意可能有自环与重边。

输出格式

共\(N\)行,每行一个非负整数,第\(i\)行输出从顶点\(1\)到顶点\(i\)有多少条不同的最短路,由于答案有可能会很大,你只需要输出\(ans \bmod 100003\)后的结果即可。如果无法到达顶点\(i\)则输出\(0\)。

输入输出样例

输入样例#1

5 7
1 2
1 3
2 4
3 4
2 3
4 5
4 5

输出样例#1

1
1
1
2
4

说明

\(1\)到\(5\)的最短路有\(4\)条,分别为\(2\)条\(1-2-4-5\)和\(2\)条\(1-3-4-5\)(由于\(4-5\)的边有\(2\)条)。

对于\(20\%\)的数据,\(N ≤ 100\);

对于\(60\%\)的数据,\(N ≤ 1000\);

对于\(100\%\)的数据,\(N<=1000000,M<=2000000\)。

分析

SPFA模板

加上一个统计数组即可

如果更新最短路,那么同时更新统计数组(注意是加法)

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)

using namespace std;
inline ll read(){
	ll f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
//**********head by yjjr**********
const int maxn=1e6+6,mod=100003;
struct edge{int to,next;}e[maxn<<1];
int last[maxn],dis[maxn],num[maxn],n,m,cnt=0,inque[maxn],que[maxn<<2];
void insert(int u,int v){e[++cnt]=(edge){v,last[u]};last[u]=cnt;}
#define v e[i].to
void SPFA(){
	mem(dis,0x3f3f3f);
	int head=0,tail=1;
	num[1]=1;dis[1]=0;inque[1]=1;que[head]=1;
	while(head<tail){
		int now=que[head++];
		reg(now){
		//	cout<<now<<' '<<e[i].to<<' '<<e[i].next<<endl;
			if(dis[v]==dis[now]+1)num[v]+=num[now],num[v]%=mod;
			else if(dis[v]>dis[now]+1){
				dis[v]=dis[now]+1;
				que[tail++]=v;inque[v]=1;
				num[v]=num[now];
			}
		}
		inque[now]=0;
	}
}
int main()
{
	n=read(),m=read();
	rep(i,1,m){
		int x=read(),y=read();
		if(x==y)continue;
		insert(x,y);insert(y,x);
	}
	SPFA();
	rep(i,1,n)cout<<num[i]<<endl;
	return 0;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr