企业官网建设流程全解析

题目描述

题目要求计算从第一个处理器向所有其他处理器广播消息所需的最短时间。给定nnn个处理器之间的通信延迟（以邻接矩阵形式给出），消息可以通过中间处理器转发，且每个处理器可以同时向多个其他处理器发送消息。需要找出从处理器111到所有其他处理器的最短路径中的最大值（即广播完成所需的最短时间）。

输入格式

第一行一个整数nnn（1≤n≤1001 \le n \le 1001≤n≤100），表示处理器的数量。
接下来若干行，输入邻接矩阵的下三角部分（不含对角线）。具体格式为：

• 第222行包含A2,1A_{2,1}A2,1​
• 第333行包含A3,1A_{3,1}A3,1​和A3,2A_{3,2}A3,2​
• 第444行包含A4,1A_{4,1}A4,1​、A4,2A_{4,2}A4,2​和A4,3A_{4,3}A4,3​
• 依此类推，直到第nnn行包含An,1A_{n,1}An,1​到An,n−1A_{n,n-1}An,n−1​

每个条目为一个整数（表示通信延迟）或字符x（表示不能直接通信）。输入保证网络是无向的，即Ai,j=Aj,iA_{i,j} = A_{j,i}Ai,j​=Aj,i​，且Ai,i=0A_{i,i} = 0Ai,i​=0。

输出格式

输出一个整数，表示从处理器111向所有其他处理器广播消息所需的最短时间。

样例

输入

5 50 30 5 100 20 50 10 x x 10

输出

35

题目分析

本题的核心是计算从源节点（处理器111）到所有其他节点的最短路径，然后取这些路径长度的最大值。由于消息可以同时沿多条路径转发，广播完成的时间取决于最慢的那条路径。

问题转化

给定nnn个节点的无向图，每条边有权重（通信延迟），节点iii到节点jjj不可达时权重视为无穷大。需要计算：
answer=max⁡2≤j≤ndist(1,j) \text{answer} = \max_{2 \le j \le n} \text{dist}(1, j)answer=2≤j≤nmax​dist(1,j)
其中dist(1,j)\text{dist}(1, j)dist(1,j)为节点111到节点jjj的最短路径长度。

算法选择

由于n≤100n \le 100n≤100，可以使用Floyd-Warshall\texttt{Floyd-Warshall}Floyd-Warshall算法（O(n3)O(n^3)O(n3)）计算所有节点对之间的最短路径，然后取第一行的最大值。也可以使用Dijkstra\texttt{Dijkstra}Dijkstra算法（O(n2)O(n^2)O(n2)或O((n+m)log⁡n)O((n + m) \log n)O((n+m)logn)）从源节点计算单源最短路径。考虑到输入规模较小，两种方法均可。

输入解析

输入只给出了邻接矩阵的下三角部分。需要正确读取这些值并构建对称的邻接矩阵：

• 对于i>ji > ji>j，读取值Ai,jA_{i,j}Ai,j​。
• 若值为x，则Ai,j=Aj,i=∞A_{i,j} = A_{j,i} = \inftyAi,j​=Aj,i​=∞（不可达）。
• 否则，Ai,j=Aj,i=读入的整数A_{i,j} = A_{j,i} = \text{读入的整数}Ai,j​=Aj,i​=读入的整数。
• 对角线元素Ai,i=0A_{i,i} = 0Ai,i​=0。

最短路径计算

使用Floyd-Warshall\texttt{Floyd-Warshall}Floyd-Warshall算法：

• 初始化dist[i][j]=∞\textit{dist}[i][j] = \inftydist[i][j]=∞，dist[i][i]=0\textit{dist}[i][i] = 0dist[i][i]=0。
• 对于每条边(u,v,w)(u, v, w)(u,v,w)，设置dist[u][v]=dist[v][u]=w\textit{dist}[u][v] = \textit{dist}[v][u] = wdist[u][v]=dist[v][u]=w。
• 三重循环更新：dist[i][j]=min⁡(dist[i][j],dist[i][k]+dist[k][j])\textit{dist}[i][j] = \min(\textit{dist}[i][j], \textit{dist}[i][k] + \textit{dist}[k][j])dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])。

计算完成后，dist[1][j]\textit{dist}[1][j]dist[1][j]即为节点111到节点jjj的最短距离。

结果

输出max⁡j=1ndist[1][j]\max_{j=1}^{n} \textit{dist}[1][j]maxj=1n​dist[1][j]（dist[1][1]=0\textit{dist}[1][1] = 0dist[1][1]=0，不影响最大值）。

复杂度分析

Floyd-Warshall\texttt{Floyd-Warshall}Floyd-Warshall时间复杂度O(n3)=106O(n^3) = 10^6O(n3)=106，n≤100n \le 100n≤100时完全可接受。

代码实现

// MPI Maelstrom// UVa ID: 423// Verdict: Accepted// Submission Date: 2016-07-17// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constlonglongMAX_TIMES=numeric_limits<int>::max();intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);longlongn,times[110][110];while(cin>>n){for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)times[i][j]=MAX_TIMES;string digits;for(inti=1;i<=n;i++)for(intj=1;j<=i-1;j++){cin>>digits;if(digits=="x")continue;else{times[i][j]=stoll(digits);times[j][i]=times[i][j];}}for(inti=1;i<=n;i++)times[i][i]=0;for(intk=1;k<=n;k++)for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)if(times[i][j]>times[i][k]+times[k][j])times[i][j]=times[i][k]+times[k][j];// from THE first node to another NODElonglongmax_delay=0;for(intj=1;j<=n;j++)max_delay=max(max_delay,times[1][j]);cout<<max_delay<<'\n';}return0;}