【BZOJ1491】社交网络
题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1491
算是Floyd的扩展吧，在求最短路的同时，记录最短路的条数。
一旦获得的任意两点间最短路的条数，就可以在O(n^3)的时间内求出每个点的l了。
提交一直出错，看了题解还是改了半天，最后才发现，题目保证任意两点间最短路条数小于10^10，但运算过程中却会爆，所以直接用double就好了。
具体的细节看代码就好了。
1 #include <cstdio> 2 #include <cstring> 3 4 const int maxn = 105, inf = 0x3f3f3f3f; 5 6 int dis[maxn][maxn]; 7 double cnt[maxn][maxn]; 8 9 int main() { 10 int n, m, a, b, c; 11 scanf("%d%d", &n, &m); 12 memset(dis, inf, sizeof(dis)); 13 for (int i = 1; i <= n; ++i) dis[i][i] = 1, cnt[i][i] = 1; 14 for (int i = 1; i <= m; ++i) { 15 scanf("%d%d%d", &a, &b, &c); 16 dis[a][b] = dis[b][a] = c; 17 cnt[a][b] = cnt[b][a] = 1; 18 } 19 for (int k = 1; k <= n; ++k) 20 for (int i = 1; i <= n; ++i) 21 for (int j = 1; j <= n; ++j) { 22 if (dis[i][j] > dis[i][k] + dis[k][j]) { 23 dis[i][j] = dis[i][k] + dis[k][j]; 24 cnt[i][j] = cnt[i][k] * cnt[k][j]; 25 } else if (dis[i][j] == dis[i][k] + dis[k][j]) 26 cnt[i][j] += cnt[i][k] * cnt[k][j]; 27 } 28 for (int k = 1; k <= n; ++k) { 29 double ans = 0; 30 for (int i = 1; i <= n; ++i) 31 for (int j = 1; j <= n; ++j) { 32 if (dis[i][j] == dis[i][k] + dis[k][j]) 33 ans += cnt[i][k] * cnt[k][j] / cnt[i][j]; 34 } 35 printf("%.3f ", ans); 36 } 37 return 0; 38 }