题目描述
战争时期,前线有 n 个哨所,每个哨所可能会与其他若干个哨所之间有通信联系。
信使负责在哨所之间传递信息,当然,这是要花费一定时间的(以天为单位)。
指挥部设在第一个哨所。
当指挥部下达一个命令后,指挥部就派出若干个信使向与指挥部相连的哨所送信。
当一个哨所接到信后,这个哨所内的信使们也以同样的方式向其他哨所送信。信在一个哨所内停留的时间可以忽略不计。
直至所有 n 个哨所全部接到命令后,送信才算成功。
因为准备充足,每个哨所内都安排了足够的信使(如果一个哨所与其他 k 个哨所有通信联系的话,这个哨所内至少会配备 k 个信使)。
现在总指挥请你编一个程序,计算出完成整个送信过程最短需要多少时间。
样例
输入样例:
4 4
1 2 4
2 3 7
2 4 1
3 4 6
输出样例:
11
Floyd算法
抽象一下题意,发现他和最短路有关系…
直接求出每一个哨所到指挥部的最短距离求MAX即可.
看到这数据范围......
不用Floyd算法简直对不起他…
时间复杂度 $O(n^3)$
C++ 代码
#include<bits/stdc++.h>
#define N 110
#define inf 0x3f3f3f3f
using namespace std;
int n,m,e[N][N],MAXN=-inf;
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
if(i==j)
e[i][j]=0;
else
e[i][j]=inf;
}
for(int i=1;i<=m;i++){
int u,v,d;
scanf("%d %d %d",&u,&v,&d);
e[u][v]=d;
e[v][u]=d;
}
for(int k=1;k<=n;k++)//Floyd标准三重循环
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(e[i][j]>e[i][k]+e[k][j])
e[i][j]=e[i][k]+e[k][j];
for(int i=1;i<=n;i++)
if(e[1][i]>MAXN)
MAXN=e[1][i];
if(MAXN==inf)//判断是否有与指挥部不相连的哨所
printf("-1\n");
else
printf("%d\n",MAXN);
return 0;
}