【BZOJ】1491: [NOI2007]社交网络（floyd）

http://www.lydsy.com/JudgeOnline/problem.php?id=1491

囧囧囧。。。。。。。。。。。。。。。。。。。。。。

囧1：虽然自己想到做法了，但是操作的时候，竟然忘记之前想到的求最短路的数量。。。（充分证实我是蒟蒻，）然后稍稍看了下题解代码。。

囧2：初始化这个梗我就T_T...还有此题精度各种爆啊。。。后2wa就是精度有问题啊囧。这题要全部开double。。要不然就。。。。我查了下double的精度，omg。。300多位。。这太爽。

此题不用说了吧，，有点最短路基础的都懂，求路径数量的时候只要判断d[i][j]==d[i][k]+d[k][j]时就根据乘法原理×上。

自环的最短路数量要=1，要不然，，你懂的。

#include <cstdio>

#include <cstring>

#include <string>

#include <iostream>

#include <cmath>

#include <algorithm>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); ++i)

#define for1(i,a,n) for(int i=(a);i<=(n);++i)

#define for2(i,a,n) for(int i=(a);i<(n);++i)

#define for3(i,a,n) for(int i=(a);i>=(n);--i)

#define for4(i,a,n) for(int i=(a);i>(n);--i)

#define CC(i,a) memset(i,a,sizeof(i))

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

#define read(a) a=getnum()

#define print(a) printf("%d", a)

inline int getnum() { int ret=0; char c; int k=1; for(c=getchar(); c<'0' || c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0' && c<='9'; c=getchar()) ret=ret*10+c-'0'; return k*ret; }

const int N=105;

double d[N][N], I[N], f[N][N];

int main() {

	int n=getnum(), m=getnum(), u, v;

	for1(i, 1, n) for1(j, 1, n) d[i][j]=1e15;

	for1(i, 1, m) read(u), read(v), scanf("%lf", &d[u][v]), d[v][u]=d[u][v], f[u][v]=f[v][u]=1;

	for1(k, 1, n) for1(i, 1, n) for1(j, 1, n) {

		if(d[i][j]>d[i][k]+d[k][j]) d[i][j]=d[i][k]+d[k][j], f[i][j]=0;

		if(d[i][j]==d[i][k]+d[k][j]) f[i][j]+=f[i][k]*f[k][j];

	}

	for1(i, 1, n) f[i][i]=0;

	for1(k, 1, n)

		for1(i, 1, n) for1(j, 1, n) if(d[i][j]==d[i][k]+d[k][j] && f[i][j]>0)

			I[k]+=f[i][k]*f[k][j]/f[i][j];

	for1(i, 1, n) printf("%.3lf\n", I[i]);

	return 0;

}

---

Description

Input

Output

输出文件包括n 行，每行一个实数，精确到小数点后3 位。第i 行的实数表 示结点i 在社交网络中的重要程度。

Sample Input

4 4
1 2 1
2 3 1
3 4 1
4 1 1

Sample Output

1.000
1.000
1.000
1.000

HINT

为1

Source