Stockbroker Grapevine
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 20558 Accepted: 11141
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.
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
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.
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
Southern African 2001
英文真的很長很難懂,但算法是很簡單的,就是一個floyd 3重循環
主要意思就是幾個炒股的要通風報信,求通風報信的最短時間(可同時通風報信給多人)
第一行就是輸入炒股的人的個數n
接下來n行
比如 第一行第一個數字是這個炒股的1號能通報給幾個人 後面的數字是給第幾號需要多少時間
第二行就是炒股的2號 blabla以此類推
注意這個傳遞方向是有向的...
求從第幾號炒股的開始傳信號 所需的時間最少 求出這個最短時間
強調一下信號能同時發出去喲,所以構建的鄰接矩陣都不用怎麼處理直接就能得出這個值
下面是詳細有注釋代碼
[cpp]
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
// freopen("in.txt","r",stdin);
int n;
while(~scanf("%d",&n) && n!=0)
{
int dis[101][101]; // 構建鄰接矩陣
int i,j,k,p;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
dis[i][j]=0x3f3f3f3f; //給所有點賦最大值
for(i=1;i<=n;i++)
{
scanf("%d",&p);
while(p--)
{
scanf("%d%d",&j,&k);
dis[i][j]=k; //兩個點的路徑(本題就是兩個投資人之間通風報信的時間)入表
}
}
/*該注釋能輸出構建的鄰接表
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
cout<<dis[i][j]<<" ";
cout<<endl;
}
*/
//開始floyd 復雜度O(n^3)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
for(k=1;k<=n;k++)
if(dis[j][k] > dis[j][i] + dis[i][k] ) //比較兩點間是 直達快 還是 繞路快,更新鄰接表
dis[j][k] = dis[j][i] + dis[i][k];
/*該注釋能輸出更新後的鄰接表
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
cout<<dis[i][j]<<" ";
cout<<endl;
}
*/
//接下來就是找出( 是哪些點能走通其他所有點 && 這些點中[到其他所有點的距離的最大值]的最小值)
int min=0x7fffffff,geti;
for(i=1;i<=n;i++)
{
int max=-0x7fffffff;
for(j=1;j<=n;j++)
{
if(i!=j && dis[i][j]>max)
max= dis[i][j];
}
if(min>max)
{
min=max;
geti=i;
}
}
cout<<geti<<" "<<min<<endl;
}
return 0;
}
作者：ffq5050139
