洛谷题单指南-最短路-P2047 [NOI2007] 社交网络

原题链接：https://www.luogu.com.cn/problem/P2047

题意解读：求经过每个点k的所有路径i->j的最短路条数 / i->j的最短路条数之和。

解题思路：最短路计数问题，且是多源最短路计数，可以借助于Floyd

设d[i][j]表示i到j的最短路，cnt[i][j]表示i到j的最短路条数，在松弛操作时可以如下更新：

if(d[i][j] > d[i][k] + d[k][j])
{
    d[i][j] = d[i][k] + d[k][j];
    cnt[i][j] = cnt[i][k] * cnt[k][j];
}
else if(d[i][j] == d[i][k] + d[k][j])
{
    cnt[i][j] += cnt[i][k] * cnt[k][j];
}

接下来，枚举每一个中间节点k，累加经过每个点k的路径i->j的最短路条数 / i->j的最短路条数

i->j的最短路条数就是cnt[i][j]

经过点k的路径i->j的最短路条数可以计算得到：cnt[i][k] * cnt[k][j]，也就是用i到k的最短路条数乘上k到j的最短路条数

而要让i->j的最短路经过k，必须符合条件：d[i][j] == d[i][k] + d[k][j]

这样就可以实现代码：

for(int k = 1; k <= n; k++)
{
    double res = 0;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(i != j && i != k && j != k && d[i][j] == d[i][k] + d[k][j])
                res += (double)cnt[i][k] * cnt[k][j] / cnt[i][j];
    cout << fixed << setprecision(3) << res << endl;
}

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 105;
long long d[N][N], cnt[N][N];
int n, m;

int main()
{
    memset(d, 0x3f, sizeof(d));
    cin >> n >> m;
    while(m--)
    {
        int u, v, w;
        cin >> u >> v >> w;
        d[u][v] = d[v][u] = w;
        cnt[u][v] = cnt[v][u] = 1;
    }
    for(int i = 1; i <= n; i++) d[i][i] = 0;
    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
            {
                if(d[i][j] > d[i][k] + d[k][j])
                {
                    d[i][j] = d[i][k] + d[k][j];
                    cnt[i][j] = cnt[i][k] * cnt[k][j];
                }
                else if(d[i][j] == d[i][k] + d[k][j])
                {
                    cnt[i][j] += cnt[i][k] * cnt[k][j];
                }
            }

    for(int k = 1; k <= n; k++)
    {
        double res = 0;
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                if(i != j && i != k && j != k && d[i][j] == d[i][k] + d[k][j])
                    res += (double)cnt[i][k] * cnt[k][j] / cnt[i][j];
        cout << fixed << setprecision(3) << res << endl;
    }

    return 0;
}