题目名称	2389. QAQ的最短路
输入输出	`boboji.in/out`
难度等级	★★★
时间限制	1000 ms (1 s)
内存限制	256 MiB
测试数据	10
题目来源	李宇航于2016-07-13加入修改该题
开放分组	全部用户
提交状态
分类标签
	分享题解

通过：26，提交：34，通过率：76.47%
李广林	100	0.000 s	0.04 MiB	C++
亚梦溪	100	0.035 s	0.43 MiB	C++
H_Lost	100	0.037 s	0.45 MiB	C
xz康	100	0.038 s	0.66 MiB	C++
李广林	100	0.042 s	0.43 MiB	C++
于静	100	0.042 s	0.43 MiB	C++
许子康	100	0.043 s	0.66 MiB	C++
李宇航	100	0.045 s	0.43 MiB	C++
LSY	100	0.045 s	0.48 MiB	C++
杨鸣宇	100	0.045 s	0.48 MiB	C++

关于 QAQ的最短路的近10条评论(全部评论)
kZime 2017-03-09 20:15 4楼
出门左转双倍经验 Sky_miner 2016-10-05 08:16 3楼
。。 _Horizon 2016-07-17 16:07 2楼
%%% Hzoi_ 2016-07-13 11:51 1楼

2389. QAQ的最短路

★★★ 输入文件：boboji.in 输出文件：boboji.out 简单对比
时间限制：1 s 内存限制：256 MiB

【题目描述】

QAQ最近遇到了一个题，是以Facebook为原型的一道NOI题，他想请你解决！

现给你一个无向图，请你求出经过节点k的 =经过k的最短路的条数/连接最短路的两个节点的最短路数！

=sum

【输入格式】

第一行是n，m分别表示节点数和边数。

接下来是m行，每行三个数u，v,dis；

分别表示两个节点以及边的权值.

【输出格式】

n行每个节点的，保留三位小数。

【样例输入】

4 4

3 2 6

4 3 1

1 3 9

4 1 1

【样例输出】

0.000

0.000

4.000

4.000

【提示】

n<=100，m<=4500。

【来源】

原谅我就这么搬过来了，NOI 2007