Stockbroker Grapevine POJ 1125 Floyd
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 37069 | Accepted: 20612 |
Description
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
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.
Output
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
3
2 2 4 3 5
2 1 2 3 6
2 1 2 2 2
5
3 4 4 2 8 5 3
1 5 8
4 1 6 4 10 2 7 5 2
0
2 2 5 1 5
0
Sample Output
3 2
3 10
Source
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
#include<string>
#include<stack>
using namespace std;
typedef long long LL;
#define MAXN 109
#define N 100
#define INF 0x3f3f3f3f
/*
所有点对其他点的最短路径中的最大值 最小的那一点!
*/
int n, k ,Min;
int g[MAXN][MAXN], maxlen[MAXN];
void Floyd()
{
for (int k = ; k <= n; k++)
{
for (int i = ; i <= n; i++)
{
for (int j = ; j <= n; j++)
{
g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}
}
}
for (int i = ; i <= n; i++)
{
for (int j = ; j <= n; j++)
{
if (j == i) continue;
maxlen[i] = max(g[i][j], maxlen[i]);
}
if (maxlen[i] < Min)
{
Min = maxlen[i], k = i;
}
}
}
int main()
{
while (scanf("%d", &n), n)
{
memset(g, INF, sizeof(g));
memset(maxlen, -, sizeof(maxlen));
int num,t,d;
for (int i = ; i <= n; i++)
{
scanf("%d", &num);
while (num--)
scanf("%d%d", &t, &d), g[i][t] = d;
}
k = -, Min = INF;
Floyd();
if (Min != INF)
printf("%d %d\n", k, Min);
else
printf("disjoint\n");
}
}
最新文章
- [c++] stack的使用
- DigitalOcean上SSH Key的创建(附DigitalOcean邀请)
- UITableView 全面详解
- 关于 IOS Runtime Runloop 2
- 从客户端(xxxxxxxxxxxxxxxxxxxxxx)中检测到有潜在危险的 Request.Form 值。
- printf code
- C++ Builder string相互转换(转)
- C语言----int (*p)[4] ---思考总结
- c++中嵌入python
- mysql用户管理及授权
- 百度地图API,展示地图和添加控件
- 潭州课堂25班:Ph201805201 第一课:环境搭建 (课堂笔记)
- numpy快速入门
- 【.NET 深呼吸】在 .net core app 中使用 Composition
- eclipse工具类及插件(设置注释模板)
- Python序列解包
- IO多路复用select/poll/epoll详解以及在Python中的应用
- HDU Humble Numbers
- jquery基础认知
- (转)有关Queue队列
热门文章
- 洛谷2019 3月月赛 T2
- [读书笔记2]《C语言嵌入式系统编程修炼》
- HDU 4135 容斥原理
- 设计模式(";大话设计模式";读书笔记 C#实现)
- PostgreSQL与MySQL比较
- 【雅虎2017】一个在线展示广告的CVR预估框架实践
- 60使用nanopim1plus查看HDMI显示分辨率的问题(分色排版)V1.0
- 自定义封装 banner 组件
- Javascript(IE快捷键操作),ASP技巧
- 崩溃通常是指操作系统向正在运行的程序发送的信号-EXC_BAD_ACCESS是信号