P1144 最短路计数
题目描述
给出一个N个顶点M条边的无向无权图，顶点编号为1～N。问从顶点1开始，到其他每个点的最短路有几条。
输入输出格式
输入格式：
输入第一行包含2个正整数N，M，为图的顶点数与边数。
接下来M行，每行两个正整数x, y，表示有一条顶点x连向顶点y的边，请注意可能有自环与重边。
输出格式：
输出包括N行，每行一个非负整数，第i行输出从顶点1到顶点i有多少条不同的最短路，由于答案有可能会很大，你只需要输出mod 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（说白了就是一个bfs），在进行最短路查询的时候判断是否出现了距离相同的路径。
#include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define N 2000000 #define mod 100003 using namespace std; queue<int>q; bool vis[N]; int n,m,x,y,tot,head[N],ans[N],dis[N]; int read() { int x=0,f=1; 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; } struct Edge { int to,next,from; }edge[N<<1]; int add(int x,int y) { tot++; edge[tot].to=y; edge[tot].next=head[x]; head[x]=tot; } int main() { n=read(),m=read(); for(int i=1;i<=m;i++) x=read(),y=read(),add(x,y),add(y,x); memset(dis,0x3f3f3f3f,sizeof(dis)); q.push(1),dis[1]=0,vis[1]=true;ans[1]=1; while(!q.empty()) { x=q.front();q.pop();vis[x]=false; for(int i=head[x];i;i=edge[i].next) { int to=edge[i].to; if(dis[to]>dis[x]+1) { dis[to]=dis[x]+1; ans[to]=ans[x]%mod; if(!vis[to]) { vis[to]=true; q.push(to); } } else if(dis[to]==dis[x]+1) { ans[to]=(ans[x]+ans[to])%mod; if(!vis[to]) { vis[to]=true; q.push(to); } } } } for(int i=1;i<=n;i++) printf("%d\n",ans[i]); return 0; }
#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<cmath> #include<algorithm> #include<queue> #include<cstdlib> using namespace std; struct Edge//邻接表存边 { int t; int nexty; }edge[3000000]; int head[2000000]={0};//邻接表的东东（存以i为发出点的编号最大的边的编号）……有人不懂吗 int cnt=0; inline void add(int a,int b)//邻接表添加边 { cnt++; edge[cnt].t=b; edge[cnt].nexty=head[a]; head[a]=cnt; } int js[2000000]={0};//每一个点的最短路径条数 int rdjs[2000000]={0};//用来避免重复的统计表，存当前在队列中，到节点i的最短路径条数 int dis[2000000];//存最短路径 bool in[2000000]={0};//是否在队列中 queue<int>spfa;//SPFA所用队列 int main() { int n,m; scanf("%d%d",&n,&m); int a,b; for(int i=0;i<m;i++) { scanf("%d%d",&a,&b); add(a,b); add(b,a);//存边 } for(int i=1;i<=n;i++)dis[i]=2e9; dis[1]=0;//初始化dis in[1]=true; js[1]=1;//1到1最短路径1条 rdjs[1]=1;//此次队列中，到1的最短路径条数为1 spfa.push(1);//将1加入队列 int curr; while(!spfa.empty()) { curr=spfa.front();//更新发出点 for(int i=head[curr];i!=0;i=edge[i].nexty)//遍历出发边 { if(dis[edge[i].t]>dis[curr]+1)//若最短路有变 { dis[edge[i].t]=dis[curr]+1;//更新最短路 rdjs[edge[i].t]=js[edge[i].t]=rdjs[curr]%100003;//以前的计数均舍弃，更新到出发点的到达路径条数 if(!in[edge[i].t]) {//加入队列 in[edge[i].t]=true; spfa.push(edge[i].t); } } else if(dis[edge[i].t]==dis[curr]+1)//若又有一条最短路 { js[edge[i].t]=(js[edge[i].t]+rdjs[curr])%100003;//增加最短路个数 rdjs[edge[i].t]=(rdjs[edge[i].t]+rdjs[curr])%100003;//在rdjs上更新，避免重复 if(!in[edge[i].t]) {//入队 in[edge[i].t]=true; spfa.push(edge[i].t); } } } in[curr]=false; rdjs[curr]=0;//此次的最短路统计已用完，将此节点的最短路条数初始化，避免重复（在此题中似乎并没有什么用） spfa.pop();//出队 } for(int i=1;i<=n;i++)printf("%d\n",js[i]);//输出 return 0; }