洛谷 1144_最短路计数_spfa

2019-11-06 07:51:16

字体：大中小

来源：转载

供稿：网友

题目描述

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

思路

因为是无权边，所以第一个走到的肯定是最短的，然后在spfa中开一个记录的数组，每次走到一个路程等于它的就加上来的那个点有多少种方法 O(KE)

#include <stdio.h>#include <queue>#define maxn 2000001#define mod 100003using namespace std;int l=0;struct arr { int x,y,w,next; };arr edge[maxn];int state[maxn],ls[maxn],f[maxn];bool exits[maxn];int spfa(){ int i; queue <int> t; t.push(1); state[1]=0; exits[1]=true; do { int tt=t.front(); t.pop(); i=ls[tt]; while (i!=0) { if (state[edge[i].x]+edge[i].w<=state[edge[i].y]) { f[edge[i].y]+=1*f[edge[i].x]; f[edge[i].y]%=mod; state[edge[i].y]=state[edge[i].x]+edge[i].w; if (exits[edge[i].y]==false) { t.push(edge[i].y); exits[edge[i].y]=true; } } i=edge[i].next; } exits[tt]=false; } while (!t.empty());}int main(){ int j,k,n,m,s; scanf("%d%d",&n,&m); for (int i=1;i<=m;i++) { l++; int x,y; scanf("%d%d",&x,&y); edge[l].x=x; edge[l].y=y; edge[l].w=1; edge[l].next=ls[edge[l].x]; ls[edge[l].x]=l; l++; edge[l].x=y; edge[l].y=x; edge[l].w=1; edge[l].next=ls[edge[l].x]; ls[edge[l].x]=l; } for (int i=1;i<maxn;i++) state[i]=0xfffffff; f[1]=1; spfa(); for (int i=1;i<=n;i++) PRintf("%d/n",f[i]);}

上一篇：洛谷 P1629 邮递员送信

下一篇：变量静态声明是否会被执行多次(static)