「Bzoj 1491」「NOI2007」社交网络 (最短路+乘法原理)

BZOJ 1491
之前一直想dij/SPFA，被次短路的思路越扯越远…看见$n$才$100$那就应该想Floyd啊。。题目挺水虽然说NOI原题。。
Floyd时顺便求路径条数，用乘法原理$num(i,j)=num(i,k) \times num(k,j)$，相同的时候不要忘了加上$num(i,k) \times num(k,j)$
之后再扫一次，找每个中转点$k$，然后继续用乘法原理，经过$k$点的路径总数为$num(i,k) \times num(k,j)$，然后统计一下就出来了

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 100 + 5;
const int INF = 1000000000;
int n, m;
int G[MAXN][MAXN];
double num[MAXN][MAXN], imp[MAXN]; 
void clean() {
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=n;j++) G[i][j] = INF, num[i][j] = 1.0;
        imp[i] = 0.0;
    }
}
void solve() {
    clean();
    for (int i=1;i<=m;i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        G[a][b] = G[b][a] = c;
    }
    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 && G[i][k] != INF && G[k][j] != INF) {
        if (G[i][j] > G[i][k] + G[k][j]) {
            G[i][j] = G[i][k] + G[k][j];
            num[i][j] = num[i][k] * num[k][j];//乘法原理
        } else if (G[i][j] == G[i][k] + G[k][j]) num[i][j] += num[i][k] * num[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 && G[i][k] != INF && G[k][j] != INF && G[i][j] != INF) {
        if (G[i][j] == G[i][k] + G[k][j]) imp[k] += (num[i][k] * num[k][j]) / num[i][j];
    }
    for (int i=1;i<=n;i++) printf("%.3f\n", imp[i]);
}
int main() {
    #ifndef ONLINE_JUDGE 
    freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
    #endif
    scanf("%d%d", &n, &m), solve();
    return 0;
}