$$\color{Purple}{kuangbin题解目录}$$
描述
机房有 $n$ 台服务器,编号 $1 \\sim n$。
其中一些服务器之间可以互相传递信息。
不同服务器之间传递信息的时间可能不同。
请你计算,从 $1$ 号服务器发出一个信息,传递到其他所有服务器,所需花费的最短时间。
输入格式
第一行包含整数 $n$。
第 $2 \\sim n$ 行,第 $i$ 行包含 $i-1$ 个正整数或字符 x
,用来描述第 $i$ 号服务器和前 $i-1$ 号服务器的连接状况。如果第 $j$ 个值 $A_{ij}$ 是正整数,则表示服务器 $i$ 和服务器 $j$ 之间可以相互传递信息,传递时间为 $A_{ij}$;如果第 $j$ 个值 $A_{ij}$ 是 x
,则表示服务器 $i$ 和服务器 $j$ 之间无法相互传递信息。
输出格式
输出一个整数,表示所需花费的最短时间。
数据范围
$1 \\le n \\le 100$,
服务器之间的传递时间取值范围 $\[1,100\]$。
保证一定有解。
输入样例:
5
50
30 5
100 20 50
10 x x 10
输出样例:
35
思路
- 求从起点$1$出发,到达
所有点
的最小时间,即分别求到达每个点的最小时间
的最大值
,故考虑采用单源最短路问题
解决;- 此题由于$n\le 100$,可采用
floyd算法
$o(n^3)$进行解决.
代码
- $Dijkstra$(朴素版)
// Problem: 传递信息
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/4246/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Date: 2023-01-26 14:37:19
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#define MAXN 110
using namespace std;
typedef long long ll;
int n;
int val[MAXN][MAXN];
int dist[MAXN],vis[MAXN];
int to_int(string s)
{
int num=0;
for(int i=0;i<s.size();i++)
num=num*10+s[i]-'0';
return num;
}
void dijkstra(int start)
{
memset(dist,0x3f,sizeof(dist));
memset(vis,0,sizeof(vis));
dist[start]=0;
for(int i=1;i<=n-1;i++)//重复进行n-1次
{
int pos=-1;//找到未标记结点中dist最小的
for(int j=1;j<=n;j++)
if(vis[j]==0&&(pos==-1||dist[j]<dist[pos]))
pos=j;
vis[pos]=1;
for(int j=1;j<=n;j++)
dist[j]=min(dist[j],dist[pos]+val[pos][j]);
}
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
cin >> n;
memset(val,0x3f,sizeof(val));
for(int i=2;i<=n;i++)
for(int j=1;j<=i-1;j++)
{
string s;
cin >> s;
if(s=="x")
continue;
val[i][j]=val[j][i]=to_int(s);
}
dijkstra(1);
int res=0;
for(int i=2;i<=n;i++)
res=max(res,dist[i]);
cout << res << endl;
return 0;
}
- $Dijkstra$(堆优化版)
// Problem: 传递信息
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/4246/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Date: 2023-01-26 14:37:19
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#define MAXN 110
#define MAXM 10010
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
int n;
int head[MAXN],ed[MAXM],val[MAXM],nex[MAXM],idx;
int dist[MAXN],vis[MAXN];
void add(int a,int b,int c)
{
ed[idx]=b;
val[idx]=c;
nex[idx]=head[a];
head[a]=idx++;
}
int to_int(string s)
{
int num=0;
for(int i=0;i<s.size();i++)
num=num*10+s[i]-'0';
return num;
}
void dijkstra(int start)
{
memset(dist,0x3f,sizeof(dist));
memset(vis,0,sizeof(vis));
dist[start]=0;
priority_queue<PII,vector<PII>,greater<PII> > q;
q.push({0,start});
while(q.size()>0)
{
PII temp=q.top();
q.pop();
int temp_dis=temp.first,temp_pos=temp.second;
if(vis[temp_pos]==1)//当前点已走过
continue;
vis[temp_pos]=1;
for(int i=head[temp_pos];i!=-1;i=nex[i])
{
int j=ed[i];
if(vis[j]==1)
continue;
if(dist[j]>temp_dis+val[i])
{
dist[j]=temp_dis+val[i];
q.push({dist[j],j});
}
}
}
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
cin >> n;
memset(head,-1,sizeof(head));
idx=0;
for(int i=2;i<=n;i++)
for(int j=1;j<=i-1;j++)
{
string s;
cin >> s;
if(s=="x")
continue;
int num=to_int(s);
add(i,j,num);
add(j,i,num);
}
dijkstra(1);
int res=0;
for(int i=2;i<=n;i++)
res=max(res,dist[i]);
cout << res << endl;
return 0;
}
- $floyd$
// Problem: 传递信息
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/4246/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Date: 2023-01-26 14:37:19
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#define MAXN 110
using namespace std;
typedef long long ll;
int n;
int val[MAXN][MAXN];
int to_int(string s)
{
int num=0;
for(int i=0;i<s.size();i++)
num=num*10+s[i]-'0';
return num;
}
void floyd()
{
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
val[i][j]=min(val[i][j],val[i][k]+val[k][j]);
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
cin >> n;
memset(val,0x3f,sizeof(val));
for(int i=2;i<=n;i++)
for(int j=1;j<=i-1;j++)
{
string s;
cin >> s;
if(s=="x")
continue;
val[i][j]=val[j][i]=to_int(s);
}
floyd();
int res=0;
for(int i=2;i<=n;i++)
res=max(res,val[1][i]);
cout << res << endl;
return 0;
}