Stockbroker Grapevine (弗洛伊德算法)
发布日期:2021-10-16 05:05:00 浏览次数:9 分类:技术文章

本文共 4061 字,大约阅读时间需要 13 分钟。

Stockbroker Grapevine

Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 20000/10000K (Java/Other)
Total Submission(s) : 28   Accepted Submission(s) : 16
Problem Description
Stockbrokers are known to overreact to rumours. You have been contracted to develop a method of spreading disinformation amongst the stockbrokers to give your employer the tactical edge in the stock market. For maximum effect, you have to spread the rumours in the fastest possible way.
Unfortunately for you, stockbrokers only trust information coming from their "Trusted sources" This means you have to take into account the structure of their contacts when starting a rumour. It takes a certain amount of time for a specific stockbroker to pass the rumour on to each of his colleagues. Your task will be to write a program that tells you which stockbroker to choose as your starting point for the rumour, as well as the time it will take for the rumour to spread throughout the stockbroker community. This duration is measured as the time needed for the last person to receive the information.
 
Input
Your program will input data for different sets of stockbrokers. Each set starts with a line with the number of stockbrokers. Following this is a line for each stockbroker which contains the number of people who they have contact with, who these people are, and the time taken for them to pass the message to each person. The format of each stockbroker line is as follows: The line starts with the number of contacts (n), followed by n pairs of integers, one pair for each contact. Each pair lists first a number referring to the contact (e.g. a '1' means person number one in the set), followed by the time in minutes taken to pass a message to that person. There are no special punctuation symbols or spacing rules.<br><br>Each person is numbered 1 through to the number of stockbrokers. The time taken to pass the message on will be between 1 and 10 minutes (inclusive), and the number of contacts will range between 0 and one less than the number of stockbrokers. The number of stockbrokers will range from 1 to 100. The input is terminated by a set of stockbrokers containing 0 (zero) people.<br><br>
 
Output
For each set of data, your program must output a single line containing the person who results in the fastest message transmission, and how long before the last person will receive any given message after you give it to this person, measured in integer minutes.<br>It is possible that your program will receive a network of connections that excludes some persons, i.e. some people may be unreachable. If your program detects such a broken network, simply output the message "disjoint". Note that the time taken to pass the message from person A to person B is not necessarily the same as the time taken to pass it from B to A, if such transmission is possible at all.
 
Sample Input
32 2 4 3 52 1 2 3 62 1 2 2 253 4 4 2 8 5 31 5 84 1 6 4 10 2 7 5 202 2 5 1 50
 
Sample Output
3 23 10
 
Source
PKU

题意:

股票传播谣言它需要特定股票经纪人和一定的时间把谣言传递给他的每一位同事。告诉您选择哪一个股票经纪人作为谣言的出发点和所花费多少时间将谣言扩散到整个社会的股票经纪人,  这一期限是衡量过去的人收到信息所需的时间。你的程序必须输出一行,包括的信息有传输速度最快的人,以及在最后一个人收到消息后,所总共使用的时间(整数分钟计算)。  你的程序可能会收到的一些关系会排除一些人,也就是有些人可能无法访问。如果你的程序检测到这样一个破碎的网络,  只需输出消息“disjoint”。请注意,所花费的时间是从A传递消息到B,B传递信息到A不一定是花费同样的传递时间,但此类传播也是可能的。 、

思路:

简单的弗洛伊德变形即可!

代码:

#include 
#include
#include
#include
#define maxn 0x3f3f3f3fusing namespace std;int mp[205][205];int main(){ int n,m,i,j,k,t,max,min; while(cin>>n,n) { /* for(i=1;i<=n;i++){ mp[i][i]=0; for(j=1;j
>m; while(m--){cin>>k>>t;mp[i][k]=t;} } for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) { if(i!=k&&j!=k&&i!=j&&mp[i][j]>mp[i][k]+mp[k][j]) mp[i][j]=mp[i][k]+mp[k][j]; } min=maxn; max=0; for(i=1;i<=n;i++) { max=0; for(j=1;j<=n;j++) { if(i==j)continue; if(mp[i][j]>max) max=mp[i][j]; } if(max

转载地址:https://blog.csdn.net/sinat_37668729/article/details/76856716 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:8月7日训练笔记
下一篇:最短路径—Dijkstra算法和Floyd算法

发表评论

最新留言

逛到本站,mark一下
[***.202.152.39]2024年03月22日 12时30分35秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

mysql slave 1062_mysql主从同步slave错误1062 2019-04-21
mysql构造器_MySQL行构造器表达式优化(Row Constructor Expression) 2019-04-21
2008日志清理 server sql_SQL Server 2008 清除日志 2019-04-21
mac mysql root 权限_Mac平台重新设置MySQL的root密码 2019-04-21
mysql新增一列_MySQL-ProxySQL中间件 2019-04-21
mysql 30入门_30分钟带你快速入门MySQL教程 2019-04-21
kangle主机怎么配置MySQL_kangle web服务+easypanel主机控制面板快速搭建网站和数据库以及管理空间详细教程... 2019-04-21
mysql 翻页 存储过程_MySQl通用翻页(存储过程) 2019-04-21
2020word替换所有文本_Excel字符函数(5):REPLACE、SUBSTITUTE查找替换函数之区别... 2019-04-21
win10安装ipython_win10环境 ipython app.py 8080 这里为什么是ipython 这步无法启动 2019-04-21
假定在MYSQL_假定在名称为教学库的数据库中包含有学生、课程和选课三个表,它们的定义如下 - 问答库... 2019-04-21
mysql多字段存储过程_mysql 的存储过程_多字段 2019-04-21
python怎么创建字符串列表_如何在python列表中为每个字符串创建子列表? 2019-04-21
vba ado 执行多条mysql 语句_access 按钮 多条sql语句 VBA 2019-04-21
弹性方法计算连续梁板内力_(梁板结构)混凝土结构设计复习题及答案 2019-04-21
java root权限_android java获得root权限调用linux命令 | 学步园 2019-04-21
java最小化窗体_JAVA窗体最大化最小化控制+托盘 2019-04-21
java 注解 数组默认值_Java注解默认值 2019-04-21
java流程语句_Java流程控制语句 2019-04-21
java require_java正则中的requireEnd和hitEnd 2019-04-21