题目链接
题目大意：n点m边无向图，Cs,t表示从s到t的不同的最短路的数目，Cs,t(v)表示经过v从s到t的最短路数目 求每个点的I
题解：比较naive的最短路计数问题 w[i][j]表示i−−j的最短路长度 p[i][j]表示i−−j的最短路条数
对p[][]的计算需要用乘法原理，这个比较显然
然后枚举每个点，计算其的贡献
我的收获：
#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int M=105; int n,m,x,y,z; long long w[M][M]; double p[M][M],ans[M]; void floyed() { for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { if(w[i][j]>w[i][k]+w[k][j]) { w[i][j]=w[i][k]+w[k][j]; p[i][j]=p[i][k]*p[k][j]; } else if(w[i][j]==w[i][k]+w[k][j]) p[i][j]+=p[i][k]*p[k][j]; } } void getans() { for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i!=j&&j!=k&&i!=k) { if(w[i][j]==w[i][k]+w[k][j]) ans[k]+=p[i][k]*p[k][j]/p[i][j]; } } void work() { floyed(); getans(); for(int i=1;i<=n;i++) printf("%.3lf\n",ans[i]); } void init() { memset(w,0x3f,sizeof(w)); cin>>n>>m; for(int i=1;i<=m;i++){ scanf("%d%d%d",&x,&y,&z); w[x][y]=w[y][x]=z; p[x][y]=p[y][x]=1; } } int main() { init(); work(); return 0; } 