第三

第二

//floyd的普通应用
#include<stdio.h>
const int maxn=110,INF=1<<29;
long long int mp[110][110],lu[110][110];//开龙龙 最后一组样例恶心 lu[][]记录i到j的路的数量
int main() {
int n,m;
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
mp[i][j]=INF;
lu[i][j]=0;
}
}
while(m--) {
int x,y,l;
scanf("%d%d%d",&x,&y,&l);
mp[x][y]=l;
mp[y][x]=l;
lu[x][y]=1;
lu[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(mp[i][j]>mp[i][k]+mp[k][j]) {//此题的重点部分（其实是小学生都能理解）
mp[i][j]=mp[i][k]+mp[k][j];
lu[i][j]=lu[i][k]*lu[k][j];
} else if(mp[i][j]==mp[i][k]+mp[k][j])
lu[i][j]+=lu[i][k]*lu[k][j];
}
}
}
for(int i=1;i<=n;i++)lu[i][i]=0;//重要 自己到自己的路可能会刚好被k更新
for(int k=1; k<=n; k++) {
double p=0;
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
if(lu[i][j] > 0 &&mp[i][j]==mp[i][k]+mp[k][j]) {
p+=lu[i][k]*lu[k][j]*1.0/lu[i][j];
}
}
}
printf("%.3f\n",p);
}
}

果然手残把long long写成long。。。
没有想到用Floyd做最短路条数的方法，于是用了一个比较怪的dp（记忆化实现），复杂度是摊还O(n^3)，可过
```c++
#include <bits/stdc++.h>
using namespace std;

int dis[101][101];
long long num[101][101];
long long dp[101];
int n, m;

struct p {
int to, dis, next;
}edge[10001];
int head[101], top = 0;

void push(int i, int j, int d)
{
edge[++top].to = j;
edge[top].dis = d;
edge[top].next = head[i];
head[i] = top;
}

long long dfs(int i, int j)
{
if (i == j) return dp[i] = 1;
if (dp[i] != -1) return dp[i];
dp[i] = 0;
for (int k = head[i]; k; k = edge[k].next) {
int to = edge[k].to, d = edge[k].dis;
if (dis[to][j] + d == dis[i][j])
dp[i] += dfs(to, j);
}
return dp[i];
}

int main()
{
memset(dis, 127/3, sizeof dis);
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
dis[i][i] = 0;
for (int i = 1; i <= m; i++) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
push(a, b, c);
push(b, a, c);
dis[a][b] = dis[b][a] = c;
}
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
dis[j][i] = dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
memset(dp, -1, sizeof dp);
dfs(i, j);
num[i][j] = dp[i];
// cout << i << " " << j << " " << dp[i] << endl;
}
for (int i = 1; i <= n; i++) {
double ans = 0;
for (int j = 1; j <= n; j++)
for (int k = 1; k <= n; k++)
if (dis[j][i] + dis[i][k] == dis[j][k] && j != i && k != i) {
ans += (double)num[j][i]*(double)num[i][k]/(double)num[j][k];
//cout << num[j][i]*num[i][k]/num[j][k] << endl;
}
//printf("%.3f\n", ans);
cout << fixed << setprecision(3) << ans << endl;
}
return 0;
}
```

###来一发裸奔之Floyd！！
令 cnt[i][j] 为从点i 到点j 的最短路径条数。
则根据 最短路径拥有***最优子结构*** 的性质 和 乘法原理，我们可以轻易得出：

1⃣. **cnt[i][j] = cnt[i][k] * cnt[k][j] ** （dist[i][j] > dist[i][k]+dist[k][j] ）
2⃣. **cnt[i][j] = cnt[i][j] + cnt[i][k] * cnt[k][j] ** （dist[i][j] == dist[i][k]+dist[k][j] ）

再令**passBy[s][t][v]** 为从点s 到 点t 且 经过 点v 的最短路径的条数。
也正是根据这个最优子结构，我们又可以明白：

3⃣. **passBy[s][t][v] = cnt[s][v] * cnt[v][t] **

（dist[s][t] == dist[s][v] + dist[v][t], 即点v 是最短路径 i~>j 上的中间点）

接下来，答案显然就是

4⃣. ans[v] = ∑ passBys[s][t][v] / cnt[s][t]

［⚠️注意！对于上述4条式子，i≠j≠k*, s≠t≠v 均成立］*
下面是代码［不要问我循环为毛挤在一行，因为本人较懒，写在一行 调试的时候按一次就过了...
##Block Code
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <string>
#include <utility>
#include <algorithm>
#include <functional>
using namespace std;

// #define LOCAL
const int Inf = 0x33333333, MaxV = 110;

int numV, numE;
int dist[MaxV][MaxV];
long long cnt[MaxV][MaxV];
double ans[MaxV];

inline void floyd() {
double sum = 0;
for (int i = 0; i <= numV; i++) for (int j = 0; j <= numV; j++) cnt[i][j] = 1;
for (int i = 0; i <= numV; i++) dist[i][i] = 0;
memset(ans, 0, sizeof(ans));
for (int k = 1; k <= numV; k++)
for (int i = 1; i <= numV; i++) {
if (k == i) continue;
for (int j = 1; j <= numV; j++) {
if (j == k || j == i) continue;
if (dist[i][j] > dist[i][k] + dist[k][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
cnt[i][j] = cnt[i][k] * cnt[k][j];
}
else if (dist[i][j] == dist[i][k] + dist[k][j])
cnt[i][j] += cnt[i][k] * cnt[k][j];
}
}
for (int v = 1; v <= numV; v++) {
for (int s = 1; s <= numV; s++) {
if (v == s) continue;
for (int t = 1; t <= numV; t++) {
if (t == v || t == s || dist[s][t] != dist[s][v] + dist[v][t]) continue;
ans[v] += (double) cnt[s][v] / cnt[s][t] * cnt[v][t];
}
}
cout << fixed << setprecision(3) << ans[v] << endl;
}
}

int main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);

int a, b, c;
cin >> numV >> numE;
memset(dist, 51, sizeof(dist));
for (int i = 0; i < numE; i++) {cin >> a >> b >> c; dist[a][b] = dist[b][a] = c;}
floyd();
return 0;
}