神马品牌网舆情应急处置预案:3、Internet消息发布（internet.???）
来源：百度文库 编辑：神马品牌网 时间：2024/05/03 06:16:40
3、Internet消息发布（internet.???）
[问题描述]
设Internet上有N个站点，通常从一个站点发送消息给其他N－1个站点，需依次发送N－1次。这样从一个站点发布消息传遍N个站点时，可能要较长时间。而当一个站点发布消息给另一个站点后，已获得消息的这两个站点就可以发布消息给另外两个站点，此后就有四个站点可以同时发布消息，这种发布消息方法应该会缩短消息传遍N个站点的时间。
请您编一个程序，设从每一个站点都可以向其他N－1个站点同时发送消息，编程求出从第一个站点开始发布消息传遍N个站点的最短时间。
输入：
由文件internet.in输入数据，文件的第一行是Internet上的站点数N（1<=N<=100），第二行起是邻接矩阵严格的下三角部分，各行是整数或字符X。A(I, J)表示从I站点发送消息给J站点所需要的时间。假设网络是无方向的，故A(I, J)＝A(J, I)，当A(I, J)＝-1时，表示从站点I不能直接向站点J发送消息；A(I,I)＝0表示没有必要自己给自己送消息（1<=I<=N），严格的下三角阵表示如下：
A(2, 1)
A(3, 1), A(3, 2)
A(4, 1), A(4, 2), A(4, 3)
┇
A(N, 1), A(N, 2)……A(N, N-1)
输出：
从屏幕上输出，输出只有一行，它是一个非负整数，若为0表示无解，非0表示合符题意的最小整数。
输入样例：
5
50
30 5
100 20 50
10 -1 -1 10
输出样例：
35
[问题描述]
设Internet上有N个站点，通常从一个站点发送消息给其他N－1个站点，需依次发送N－1次。这样从一个站点发布消息传遍N个站点时，可能要较长时间。而当一个站点发布消息给另一个站点后，已获得消息的这两个站点就可以发布消息给另外两个站点，此后就有四个站点可以同时发布消息，这种发布消息方法应该会缩短消息传遍N个站点的时间。
请您编一个程序，设从每一个站点都可以向其他N－1个站点同时发送消息，编程求出从第一个站点开始发布消息传遍N个站点的最短时间。
输入：
由文件internet.in输入数据，文件的第一行是Internet上的站点数N（1<=N<=100），第二行起是邻接矩阵严格的下三角部分，各行是整数或字符X。A(I, J)表示从I站点发送消息给J站点所需要的时间。假设网络是无方向的，故A(I, J)＝A(J, I)，当A(I, J)＝-1时，表示从站点I不能直接向站点J发送消息；A(I,I)＝0表示没有必要自己给自己送消息（1<=I<=N），严格的下三角阵表示如下：
A(2, 1)
A(3, 1), A(3, 2)
A(4, 1), A(4, 2), A(4, 3)
┇
A(N, 1), A(N, 2)……A(N, N-1)
输出：
从屏幕上输出，输出只有一行，它是一个非负整数，若为0表示无解，非0表示合符题意的最小整数。
输入样例：
5
50
30 5
100 20 50
10 -1 -1 10
输出样例：
35