题目描述(ID:12253)
标题: 城市规划
标签: 动态规划
详情: N 城准备开发一片荒地,目前已经规划好了一些居民点,还要建些道路。由于经费问题,他们想在任意两点间的距离最短的前提下,用尽可能少的投资把各个点连接起来。需要注意的是并不是任意两个居民点间都能直接相连给出两两居民点间建路的花费(与长度成正比),你可以帮他们选择一个最佳方案吗?
输入格式:
第一行是一个数 N(N<100),表示有 N 个居民点。
以下的 N 行每行有 N 个数,第 i 行第 j 个数表示居民点 i 到居民点 j 间
建路的花费 wij(0
输出格式:
第一行输出总花费。
然后输出 N 行,每行 N 个数第 i 行第 j 个数表示居民点 i 到居民点 j 的
路,用 1 表示选取这条路,0 则不选。
样例:

输入

3
0 2 1
2 0 3
1 3 0

输出

3
0 1 1
1 0 0
1 0 0
登录并解答