#include<bits/stdc++.h>
#define INF 1e9
#define N 109
using namespace std;
typedef long long ll;
ll n,m,a,b,d[N][N],cnt[N][N];;// n,m,a,b,c,d[i][j],cnt[i][j]是长整数变量,代表点数,边数,输入用的三个变量,从i到j的最短路,从i到j的最短路数量
double ans;
int main(){
freopen("socialnetwork.in","r",stdin);
freopen("socialnetwork.out","w",stdout);
cin>>n>>m;
fill(d[0],d[0]+109*109,INF);
for(ll i=1;i<=m;i++){
cin>>a>>b;
cin>>d[a][b];
d[b][a]=d[a][b];
cnt[a][b]=cnt[b][a]=1;

}
for(ll k=1;k<=n;k++){
for(ll i=1;i<=n;i++){
for(ll j=1;j<=n;j++){
ll cost=d[i][k]+d[k][j];
if(cost==d[i][j]){
cnt[i][j]+=cnt[i][k]*cnt[k][j];
}
else if(cost<d[i][j]){
cnt[i][j]=cnt[i][k]*cnt[k][j];
d[i][j]=cost;
}
}
}
}
for(ll v=1;v<=n;v++){
ans=0;
for(ll s=1;s<=n;s++)if(s!=v){
for(ll t=1;t<=n;t++)if(s!=t&&v!=t){
if(d[s][t]==d[s][v]+d[v][t]){
ans+=1.*cnt[s][v]*cnt[v][t]/cnt[s][t];
}
}
}
cout<<fixed<<setprecision(3)<<ans<<endl;
}
return 0;
}

Floyd用起来不太顺手所以跑了N遍Dijkstra
#include <cstdio>
#include <cstring>
#include <algorithm>

typedef long long longint;

const int maxN=105;
const int inf=0x3f3f3f3f;

int N,M;
int adj[maxN][maxN];
longint cnt[maxN][maxN];
int dist[maxN][maxN];
bool vis[maxN];

void initGraph()
{
memset(adj,0x3f,sizeof(adj));
memset(cnt,0,sizeof(cnt));
memset(dist,0x3f,sizeof(dist));
}

void input()
{
initGraph();
scanf("%d%d",&N,&M);
int u,v,w;
for(int i=1;i<=M;i++)
{
scanf("%d%d%d",&u,&v,&w);
adj[u][v]=adj[v][u]=w;
}
}

void initDijkstra(int st)
{
memset(vis,0,sizeof(vis));
dist[st][st]=0;
cnt[st][st]=1;
}

void dijkstra(int st)
{
initDijkstra(st);
int cur=st;
for(int i=1;i<N;i++)
{
vis[cur]=true;
for(int j=1;j<=N;j++) if(!vis[j])
{
if(dist[st][cur]+adj[cur][j]<dist[st][j])
{
dist[st][j]=dist[st][cur]+adj[cur][j];
cnt[st][j]=cnt[st][cur];
}
else if(dist[st][cur]+adj[cur][j]==dist[st][j])
cnt[st][j]+=cnt[st][cur];
}
int minDist(inf);
for(int j=1;j<=N;j++)
if(!vis[j] && dist[st][j]<minDist)
{
cur=j;
minDist=dist[st][j];
}
}
}

double calcI(int x)
{
double ans(0.0);
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++) if(i!=x && j!=x) {
if(dist[i][x]+dist[x][j]==dist[i][j])
ans+=(1.0*cnt[i][x]/cnt[i][j]*cnt[x][j]);
}

return ans;
}

void solve()
{
for(int i=1;i<=N;i++) dijkstra(i);
for(int i=1;i<=N;i++) printf("%.3f\n",calcI(i));
}

int main()
{
input();
solve();
return 0;
}

Dijkstra都秒了……
```c++
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int maxn = 200;

struct Ed
{
int from,to,dis;
Ed(int a=0,int b=0,int c=0) : from(a),to(b),dis(c) {}
};

struct Po
{
int d,dis;
Po(int a=0,int b=0): d(a),dis(b) {}
bool operator< (const Po &a) const { return dis>a.dis || (dis==a.dis&&d>a.d); }
};

vector<Ed> edges;
vector<int> G[maxn];
int n,m,min_dis[maxn][maxn];
bool done[maxn];
double ans[maxn];
long long int path_num[maxn][maxn];
priority_queue<Po> q;

void Dijkstra(int s)
{
memset(done,0,sizeof(done));
while(!q.empty()) q.pop();
min_dis[s][s]=0;
path_num[s][s]=1;
q.push(Po(s,0));

while(!q.empty())
{
int now=(q.top()).d;q.pop();
if(done[now]) continue;
done[now]=true;

for(int i=0;i<(int)G[now].size();i++)
{
Ed& e=edges[G[now][i]];
if(min_dis[s][e.to]==min_dis[s][now]+e.dis)
path_num[s][e.to]+=path_num[s][now];
if(min_dis[s][e.to]>min_dis[s][now]+e.dis||min_dis[s][e.to]==-1)
{
min_dis[s][e.to]=min_dis[s][now]+e.dis;
path_num[s][e.to]=path_num[s][now];
q.push(Po(e.to,min_dis[s][e.to]));
}
}
}
}

inline void add_edges(int a,int b,int dis)
{
edges.push_back(Ed(a,b,dis));
edges.push_back(Ed(b,a,dis));
int k=edges.size();
G[a].push_back(k-2);
G[b].push_back(k-1);
}

int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add_edges(a,b,c);
}

memset(min_dis,-1,sizeof(min_dis));
for(int i=1;i<=n;i++)
Dijkstra(i);

/*int a,b;
while(scanf("%d%d",&a,&b)&&a!=0&&b!=0)
{
printf("%d %lld\n",min_dis[a][b],path_num[a][b]);
printf("%d %lld\n",min_dis[b][a],path_num[b][a]);
}*/

memset(ans,0,sizeof(ans));

for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
if(i!=j&&i!=k&&j!=k&&min_dis[j][i]+min_dis[i][k]==min_dis[j][k])
ans[i]+=(double)(path_num[j][i]*path_num[i][k])/(double)path_num[j][k];

for(int i=1;i<=n;i++)
printf("%.3lf\n",ans[i]);
return 0;
}

/*Accepted, time = 75 ms, mem = 1232 KiB, score = 100*/
```

Floyd http://www.cnblogs.com/JSZX11556/p/5147891.html

测试数据 #0: Accepted, time = 0 ms, mem = 400 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 400 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 400 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 400 KiB, score = 10

测试数据 #4: Accepted, time = 0 ms, mem = 396 KiB, score = 10

测试数据 #5: Accepted, time = 15 ms, mem = 396 KiB, score = 10

测试数据 #6: Accepted, time = 15 ms, mem = 400 KiB, score = 10

测试数据 #7: Accepted, time = 15 ms, mem = 396 KiB, score = 10

测试数据 #8: Accepted, time = 15 ms, mem = 400 KiB, score = 10

测试数据 #9: Accepted, time = 0 ms, mem = 396 KiB, score = 10

Accepted, time = 60 ms, mem = 400 KiB, score = 100

代码

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

int dist[100 + 2][100 + 2];
long long num[100 + 2][100 + 2];
int n , m , a , b , c;
double ans;

int main()
{
cin >> n >> m;
memset( dist , 1 , sizeof( dist ) );
for( register int i = 1 ; i <= m ; i++ )
{
scanf( "%d %d %d" , &a , &b , &c );
dist[a][b] = dist[b][a] = c;
num[a][b] = num[b][a] = 1;
}
for( register int k = 1 ; k <= n ; k++ )
for( register int i = 1 ; i <= n ; i++ )
for( register int j = 1 ; j <= n ; j++ )
if( dist[i][j] > dist[i][k] + dist[k][j] )
{
dist[i][j] = dist[i][k] + dist[k][j];
num[i][j] = num[i][k] * num[k][j];
}
else if( dist[i][j] == dist[i][k] + dist[k][j] )
num[i][j] += num[i][k] * num[k][j];
for( register int i = 1 ; i <= n ; i++ ) num[i][i] = 0;
for( register int k = 1 ; k <= n ; k++ )
{
ans = 0;
for( register int i = 1 ; i <= n ; i++ )
for( register int j = 1 ; j <= n ; j++ )
if( num[i][j] > 0 && dist[i][j] == dist[i][k] + dist[k][j] )
ans += ( double )num[i][k] * num[k][j] / num[i][j];
printf( "%.3f\n" , ans );
}
return 0;
}
%lf就WA0了%f就AC了。。。

这么水的题目。。。NOI2007。。。直接用两个O(N^3)的循环就解决了。。。

第一次没用int64挂了。。。显示的居然是错误200。。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

NOI可以用int64么？

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

没啥好说的

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

通过 　　66人

FLOYD先求出dis。

sum[i][j]表示i~j最短路数量，则

sum[i][j]=sigma(sum[i][k]|dis[i][k]+map[k][j]=dis[i][j])

然后用sum求出Cs,t(v)即可

近乎裸的Floyd

int64极度猥琐~

很简单的题目~

由于数据范围很小，用floyd即可，不过考虑此题的特殊性，需在floyd算法中做一些改动，还需运用加法原理和乘法原理，细心是最主要的~

题目有点繁琐，大家耐心做哦~

沙茶题，floyd

我要自杀，Floyd都能写错……………………

祈祷今年NOI能有这样的题目

桥 神 最硬啊！！！！！！！！！！！！！！！！！

很简单

(不过要注意用int64)

用 floyd 可以秒杀哦~~

占个位置先!

地下室2层

极度猥琐~

!!!!!!!!!!

NOI前最后一题.