codevs 5960 信使x
2024-09-05 14:42:48
题目描述 Description
•战争时期,前线有n个哨所,每个哨所可能会与其他若干个哨所之间有通信联系。信使负责在哨所之间传递信息,当然,这是要花费一定时间的(以天为单位)。指挥部设在第一个哨所。当指挥部下达一个命令后,指挥部就派出若干个信使向与指挥部相连的哨所送信。当一个哨所接到信后,这个哨所内的信使们也以同样的方式向其他哨所送信。直至所有n个哨所全部接到命令后,送信才算成功。因为准备充足,每个哨所内都安排了足够的信使(如果一个哨所与其他k个哨所有通信联系的话,这个哨所内至少会配备k个信使)。 • 现在总指挥请你编一个程序,计算出完成整个送信过程最短需要多少时间
输入描述 Input Description
•第1行有两个整数n和m,中间用1个空格隔开,分别表示有n个哨所和m条通信线路。1<=n<=100。 • 第2至m+1行:每行三个整数i、j、k,中间用1个空格隔开,表示第i个和第j个哨所之间存在通信线路,且这条线路要花费k天。
输出描述 Output Description
仅一个整数,表示完成整个送信过程的最短时间。如果不是所有的哨所都能收到信,就输出-1。
样例输入 Sample Input
•4 4 •
1 2 4 •
2 3 7 •
2 4 1 •
3 4 6
样例输出 Sample Output
11
数据范围及提示 Data Size & Hint
1<=n<=100
分类标签 Tags 点此展开
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int map[][];
int maxn=0x7f;
int main()
{
memset(map,maxn,sizeof(map));
int n,m;
cin>>n>>m;
for(int i=; i<=m; i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
map[x][y]=map[y][x]=z;
}
map[][]=;
for(int k=; k<=n; k++)
{
for(int i=; i<=n; i++)
{
for(int j=; j<=n; j++)
{
if(map[i][j]>map[i][k]+map[k][j])
{
map[i][j]=map[i][k]+map[k][j];
}
}
}
}
int ans=-;
for(int i=;i<=n;i++)
{
if(map[][i]>ans)
{
ans=map[][i];
}
else
{
if(map[][i]==maxn)
{
cout<<"-1";
return ;
}
}
}
cout<<ans;
return ;
}
最新文章
- <;<;<; html编码中js和html编码不一致导致乱码
- putty+xming远程登录Ubuntu16.04图形界面
- Android自定义控件3--优酷菜单执行动画
- JAVA单例
- 提高AdoQuery的速度
- transient关键字使用笔记
- ci(转)
- 小米2000万买域名mi.com
- FTP服务器简易有效的访问方法
- Sql中联合查询中的”子查询返回的值不止一个“的问题
- UVA 10759 Dice Throwing
- Owl Carousel幻灯片插件的使用
- 【重学计算机】机组D4章:存储系统
- css 中 zoom和transform:scale的区别(转载)
- android开发_文本按钮 与 输入框
- 针对IE9的CSS兼容
- IIS Express
- 认真研究下HTML之id、name、form、submit
- hihocoder [Offer收割]编程练习赛12 [1494] ---- 一面砖墙
- IIS安全加固