网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
城市规划
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | cityroad.in | 输出文件 | cityroad.out |
【问题描述】
N城准备开发一片荒地,目前已经规划好了一些居民点,还要建些道路。由于经费问题,他们想在任意两点间的距离最短的前提下,用尽可能少的投资把各个点连接起来。需要注意的是并不是任意两个居民点间都能直接相连。给出两两居民点间建路的花费(与长度成正比),你可以帮他们选择一个最佳方案吗?
N城准备开发一片荒地,目前已经规划好了一些居民点,还要建些道路。由于经费问题,他们想在任意两点间的距离最短的前提下,用尽可能少的投资把各个点连接起来。需要注意的是并不是任意两个居民点间都能直接相连。给出两两居民点间建路的花费(与长度成正比),你可以帮他们选择一个最佳方案吗?
【输入格式】
第1行是一个数N(N<100),表示有N个居民点。
以下的N行每行有N个数,第i行第j个数表示居民点i到居民点J问建路的花费(O<wij<10000,wij=wij,非正数表示两地不可直连。输入数据保证有解。
以下的N行每行有N个数,第i行第j个数表示居民点i到居民点J问建路的花费(O<wij<10000,wij=wij,非正数表示两地不可直连。输入数据保证有解。
【输出格式】
第1行输出总花费。
然后输出N行,每行N个数,第i行第j个数表示居民点i到居民点j的路,用1表示先取这条路,0则不选。
然后输出N行,每行N个数,第i行第j个数表示居民点i到居民点j的路,用1表示先取这条路,0则不选。
【输入输出样例】
输入(cityroad.in)
3
0 2 1
2 0 3
1 3 0
输出(cityroad.out)
输入(cityroad.in)
3
0 2 1
2 0 3
1 3 0
输出(cityroad.out)
3
0 1 1
1 0 0
1 0 0
0 1 1
1 0 0
1 0 0