[SHOI2009] 交通网络

题目描述

著名的城市交通规划师L.Serenade为OItown的各个城堡之间设计了一套的地铁交通网络。每一条地铁线路都用来双向连通两个城堡。因为是建在地下的不同深度，所以这些地铁线路是可以“交叉”的。 OItown的居民们的生活和工作都在不同的城堡中进行，于是，每个OItown的居民都要在每天早晨从家出发，乘地铁去工作，当然地铁换乘是允许的。不过每个居民都会选择换乘次数最少的乘车方式。如果有多种乘车方式，这些乘车方式所需要的换乘次数一样，那么居民每天都会等概率的随机选择其中一种。现在L.Serenade想请你为他计算出，每天每条地铁线路在早晨的平均客流量。他会告诉你，每个居民的家和工作地址，还有他设计的地铁交通网络的全部信息。当然L.Serenade保证，交通网络能把城市连为一体，而且任意两个城堡之间的最优乘车方式（即换成次数最少的）不超过263-1种。

---

输入格式

输入文件的第一行有两个整数n、m，分别表示OItown里的城堡数（这些城堡用1.2.3...n标号）和地铁线路的数量。接下去m行，每行包含两个整数，x、y，表示这两个城堡之间有一条地铁线路。注意，两个城堡之间最多只有一条地铁线路，且每条地铁线路只被输入文件描述一次。最后的n行，每行有n个整数。第i行的第j个非负整数Ci，j表示每天早晨有Ci，j个OItown的居民要从i城堡去j城堡。输入数据保证Ci，i=0。

---

输出格式

输出文件有m行，每行依次表示每条地铁线路每天早晨的平均客流。精确到小数点后一位。整数也应输出一位小数，例如1应输出为1.0。

---

样例输入

6 7
1 2
1 3
2 4
2 5
3 5
4 6
5 6
0 0 0 0 0 1
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

---

样例输出

0.7
0.3
0.3
0.3
0.3
0.3
0.3
0.7

---

提示

样例说明：从城堡1到城堡六的使得换乘次数最少的乘车方式共有3种：1-2-4-6；1-2-5-6；1-3-5-6。所以每个人都有1/3的概率选择这其中的每一种。 N< = 300 M< = N*(N-1) div 2 0< = C(i,j) < = 100

---

题目来源

Day1