（ssl 1500）最短路上的统计#floyd#

本文主要是介绍（ssl 1500）最短路上的统计#floyd#，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

一个无向图上，没有自环，所有边的权值均为1，对于一个点对（a,b）,我们要把所有a与b之间所有最短路上的点的总个数输出。

分析：

求最短路径经过的点数
首先floyd是很简单的，
$f[i][j]=min(f[i][j],f[i][k]+f[k][j])$
然后就会想到它既然赋值了，$f[i][j]=f[i][k]+f[k][j]$就说明它经过了这个点。

代码

#include <cstdio>
#include <cstring>
using namespace std;
int n,m,x,y,ans[101][101],g[101][101];
int main(){scanf("%d%d",&n,&m);memset(g,0x7f,sizeof(g));for (int i=1;i<=m;i++){scanf("%d%d",&x,&y);g[x][y]=1;g[y][x]=1;}for (int k=1;k<=n;k++)for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)if (i!=j&&i!=k&&j!=k)if (g[i][j]>(long long)g[i][k]+g[k][j]) g[i][j]=g[i][k]+g[k][j];for (int k=1;k<=n;k++)for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)if (i!=j&&i!=k&&j!=k)if (g[i][j]==(long long)g[i][k]+g[k][j]) ans[i][j]++;scanf("%d",&m);for (int i=1;i<=m;i++)scanf("%d%d",&x,&y),printf("%d\n",ans[x][y]+2);//起始点和终点+2return 0;
}

这篇关于（ssl 1500）最短路上的统计#floyd#的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---