人流统计
   

　　问题描述：

　　小明是WH市长的全权顾问。最近，市长在对WH城市进行新的规划，希望能拓宽一些人流密度较大的街道，改善交通。

　　WH城市是由N×M个方格组成的，一些方格是建筑物，用X表示；一些方格是街道，用 . 表示；还有一些方格是人流的出发地和目的地，用字母A~O表示。例如下面是一个4×4的城市平面图，有两个人流入口（出口）：A和B。
　　　　　　　　　　　....
　　　　　　　　　　　A.X.
　　　　　　　　　　　XXX.
　　　　　　　　　　　B...

　　交通部门搜集了在某段时间内人群的流动情况，并以若干个三元组(S1，S2，C)表示。　

　　(S1,S2,C)记录有C个单位人流从S1出发，目的地是S2。其中，S1和S2是字母A~O，表示入口（出口），C为实数。

　　从S1出发，到S2的人流会按照以下规则移动：

　　l.人流只能往东，南，西，北四个方向移动；
　　2.人流除了出发时和结束时，在移动过程中只能经过"街道"；
　　3.人流将选择从S1到S2的最短路径来移动；
　　4.如果从S1到S2有多条最短路径--设为K条（保证K不超过2^30），则人流量C将分成K等份，每一条最短路径有C/K人流经过。

　　作为市长的顾问，交通部门会给小明一份城市的平面图和某段时间的人流情况。小明被要求统计出在这段时间内，每条街道总共被多少人流经过。
　　
　　输入文件：flow.in

　　输入文件的第一行有两个数：N和M，表示城市平面图的规模。（1<N,M<25）
　　以下N行，每行M个字母，描述了一个城市平面图。
　　接下来描述的是人流情况，每行一个三元组：S1S2 C。（S1，S2为字母,C为实数），特殊的XX 0将表示文件结束。
　　
　　输出文件：flow.out

　　输出文件有N行，每行M个实数，表示街道的人流情况，精确到小数点后两位。每个实数输出占7个字节，不足的在之前以空格补充（见样例）。
　
　　样例输入：flow.in

　　4 4
　　...
　　A.X.
　　XXX.
　　B...
　　AB 2
　　BA 1
　　XX 0

　　样例输出：flow.out

　　1.50 3.00 3.00 3.00
　　0.00 1.50 0.00 3.00
　　0.00 0.00 0.00 3.00
　　0.00 3.00 3.00 3.00
　 		   

 
网站导航 | 关于曙光 | 联系我们 | 请提意见
Copyright © FuJian Sunshine Educational Info. Co.,Ltd.
福建曙光教育资讯有限公司 版权所有