Empire Problem

上周以前大学同学分享探讨了一个编程问题，觉得还是挺有典型意义的（解法与题意理解上）。故在此记录下。

Problem
The empire has a capitol and a number of cities. Some cities are connected to other cities. A route connecting two cities can transport a message in both directions. All cities are reachable using some path from the capitol city. The connections among all cities are described in an adjacency matrix with the format shown below. At the start, a message is sent from the capitol city to all other cities, and we want to know what’s the minimal time for a message to spread out from the capitol to the whole empire.

Sample
Input
5
50
30 5
100 20 50
10 x x 10

Output
35

如何输入：

首先输入一个n值（输入第一行），1<=n<=100，然后输入消息在城市之间传递的消息矩阵（均为整形），在输入第二行输入Cost(2,1)，表示城市2到城市1的消息传递耗时，第三行输入Cost(3.1)，Cost(3.2)，分别表示城市3到城市1与城市3到城市2的消息传递耗时，第四行、第五行以及后续依次类推。其中城市1作为消息的起始点，即empire。

取值规则：

1.Cost(i,j) == Cost(j,i)，表示城市i到城市j与城市j到城市i的消息传递耗时相等；
2.Cost(i,j) == z，表示城市i到城市j之间没有通路；
3.Cost(i,i) == 0，城市内部传递耗时为0；

sample的连接图：

题意理解与解答：

注意这一句，At the start, a message is sent from the capitol city to all other cities, and we want to know what’s the minimal time for a message to spread out from the capitol to the whole empire.，结合sample的output(35)可以推断出从capitol city可以向不同的城市发出多条message，然后得到message传遍所有城市的最小耗时。

Cost(1,2) = 1->3->2 = 30 + 5 = 35
Cost(1,3) = 1->3 = 30
Cost(1,4) = 1->5->4 = 10 + 10 = 20
Cost(1,5) = 1->5 = 10

故所有message传遍所有城市的最短时间是35，解题的思路类似地图上求一点到其他点最短路径问题，具体可以参考Dijkstra算法。
整个题目解答，用C实现：empire_problem_some_messages.c

---

这里有争论点的地方是对上述英文的理解，a message，会理解成为只有一条message从capitol city发出，然后传播到其他所有的城市。那么Sample解法变成：

Least Cost = 1->5->4->2->3 = 10 + 10 + 20 + 5 = 45

若这样理解题意a message传遍所有城市的最短时间是45，解题思路和上面有很大区别，涉及到部分回溯。
此时的题目解答，用C实现：empire_problem_one_message.c

（全文结束）

转载文章请注明出处：漫漫路 - lanindex.com