常规的最短路计数问题：注意有重边（重边不用理，看样例），自环（读入时过滤）。
另外这个无向图没有权，其实可以直接bfs做，但考虑到以后带权的情况，按spfa走了。
水题被卡了三次（嘤嘤嘤
第一次40pts：忘取膜了（？？？
第二次80pts：加了多余的判断，实质还是思路不清晰。
第三次100pts：去了冗余的判断，终于A了。
思路：
记录f数组表示f[i]为以i为终点，1为起点的最短路条数。初始只有f[1]=1。
其余在松弛的时候如果更新，f[v]=f[u]；
如果恰好相等（有相同最短路径）（这种情况不能和上面的情况一起判断），就f[v]+=f[u]
Code
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 const int inf=2147483647; 8 int n,m,s; 9 int p=100003;10 int num;11 int pre[1000090],f[1000090];12 struct node{13 int to,val,next;14 }edge[4000090];15 int dis[1000090];16 bool visit[1000090];17 void add(int x,int y,int z)18 {19 num++;20 edge[num].val=z;21 edge[num].to=y;22 edge[num].next=pre[x];23 pre[x]=num;24 }25 void spfa()26 {27 queue q;28 for(int i=1;i<=n;i++)29 dis[i]=inf;30 q.push(1);31 dis[1]=0;f[1]=1;32 visit[1]=1;33 while(!q.empty())34 {35 int u=q.front();36 q.pop();37 visit[u]=0;38 for(int i=pre[u];i>0;i=edge[i].next)39 {40 int v=edge[i].to;41 //if(u==1) (f[v]=1)%=p;42 if(dis[v]>dis[u]+edge[i].val)43 {44 dis[v]=dis[u]+edge[i].val;45 /*if(u!=1)*/ (f[v]=f[u])%=p;46 if(visit[v]==0)47 {48 visit[v]=1;49 q.push(v);50 }51 }52 else if(dis[v]==dis[u]+edge[i].val)53 (f[v]+=f[u])%=p; 54 }55 }56 }57 int main()58 {59 scanf("%d%d",&n,&m);60 for(int i=1;i<=m;i++)61 {62 int x=0,y=0,z=0;63 scanf("%d%d",&x,&y);64 if(x==y) continue;65 add(x,y,1);66 add(y,x,1); 67 }68 spfa();69 for(int i=1;i<=n;i++)70 printf("%d\n",f[i]);71 return 0;72 }
* Update 2018.9.22
做NOIp2017逛公园的时候发现自己的最短路计数算法有些Bug==
导致30分没有成功拿到。
做了一道加强版的最短路计数
1 #include2 #include 3 #include 4 #include 5 6 using namespace std; 7 typedef long long ll; 8 9 int n,m,fake;10 int vis[2090],dis[2090];11 ll f[2090];12 int e[2090][2090];13 14 void spfa()15 {16 memset(dis,63,sizeof(dis));17 fake=dis[233];18 queue q;19 q.push(1);vis[1]=1;dis[1]=0;f[1]=1;20 while(!q.empty())21 {22 int u=q.front();q.pop();23 vis[u]=0;24 if(u==n) continue;25 for(int i=1;i<=n;i++)26 {27 if(dis[i]==dis[u]+e[u][i])28 f[i]+=f[u];29 if(dis[i]>dis[u]+e[u][i])30 {31 dis[i]=dis[u]+e[u][i];32 f[i]=f[u];33 }34 if(f[i]&&!vis[i]) vis[i]=1,q.push(i); 35 }36 f[u]=0;37 }38 }39 40 int main()41 {42 scanf("%d%d",&n,&m);43 memset(e,63,sizeof(e));44 for(int i=1;i<=m;i++)45 {46 int x=0,y=0,z=0;47 scanf("%d%d%d",&x,&y,&z);48 e[x][y]=min(e[x][y],z);49 }50 spfa();51 if(fake==dis[n]) printf("No answer");52 else printf("%d %lld",dis[n],f[n]);53 return 0;54 }
还是用这个吧qwq