Stockbroker Grapevine
Time Limit: 1000MS
Memory Limit: 10000K
Total Submissions: 20810
Accepted: 11278
Description
Stockbrokers are known to overreact to rumours. You havebeen contracted to develop a method of spreading disinformation amongst thestockbrokers to give your employer the tactical edge in the stock market. Formaximum 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 thestructure of their contacts when starting a rumour. It takes a certain amountof time for a specific stockbroker to pass the rumour on to each of hiscolleagues. Your task will be to write a program that tells you whichstockbroker to choose as your starting point for the rumour, as well as thetime it will take for the rumour to spread throughout the stockbrokercommunity. This duration is measured as the time needed for the last person toreceive the information.
Input
Your program willinput data for different sets of stockbrokers. Each set starts with a line withthe number of stockbrokers. Following this is a line for each stockbroker whichcontains 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 ofeach stockbroker line is as follows: The line starts with the number ofcontacts (n), followed by n pairs of integers, one pair for each contact. Eachpair lists first a number referring to the contact (e.g. a '1' means personnumber one in the set), followed by the time in minutes taken to pass a messageto that person. There are no special punctuation symbols or spacing rules.
Each person is numbered 1 through to the number of stockbrokers. The time takento pass the message on will be between 1 and 10 minutes (inclusive), and thenumber of contacts will range between 0 and one less than the number ofstockbrokers. The number of stockbrokers will range from 1 to 100. The input isterminated by a set of stockbrokers containing 0 (zero) people.
Output
For each set of data, your program must output a singleline containing the person who results in the fastest message transmission, andhow long before the last person will receive any given message after you giveit to this person, measured in integer minutes.
It is possible that your program will receive a network of connections thatexcludes some persons, i.e. some people may be unreachable. If your programdetects 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 notnecessarily the same as the time taken to pass it from B to A, if such transmissionis 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 African2001
題意：
這個題目到不會難，只是題意挺難理解的，大概講的是消息在傳送，第一行給出消息傳送的人數n，接下來n行中的第一個數字表示第i個人可以傳遞以m個人（a,b）表示傳遞的編號和時間，問從那個人傳送的時間會最快，時間是多少，同一個人傳遞給多個人時間只算一個最大的。
解題思路：
因為這個題目的數據量比較小，可以用Floyd-Warshall算法來做，這個算法求出每兩個點之間的最小距離，在遍歷一遍答案就可以出來了
代碼：
#include <iostream>
#include<cstdio>
#include<cstring>
#define MAX 103
#define VALUE 0xffffff
using namespace std;
int g[MAX][MAX];
int d[MAX];
bool used[MAX];
int min(int x,int y)
{
return x<y?x:y;
}
void Floyd(int n)
{
int i,j,k;
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
g[i][j]=min(g[i][j],g[i][k]+g[k][j]);//求出任意兩點之間的最小值
}
int main()
{
int ts;
int i,j;
int maxvalue,maxtime,t;
while(true)
{
scanf("%d",&ts);
if(ts==0)break;
// memset(g,0,sizeof(g));
for(i=1;i<=ts;i++)
for(j=1;j<=ts;j++)
g[i][j]=VALUE;
for(i=1;i<=ts;i++)
{
int n;
scanf("%d",&n);
g[i][i]=0;
while(n--)
{
int no,time;//時間和編號
scanf("%d%d",&no,&time);
g[i][no]=time;//建圖
}
}
Floyd(ts);
maxtime=VALUE;
for(i=1;i<=ts;i++)
{
maxvalue=0;
for(j=1;j<=ts;j++)
{
if(g[i][j]>maxvalue)
{//求出最長的邊
maxvalue=g[i][j];
}
}
if(maxvalue<maxtime)
{
maxtime=maxvalue;
t=i;
}
}
if(maxtime==VALUE)
{
printf("disjoint\n");
}
else
{
printf("%d %d\n",t,maxtime);
}
}
return 0;
}
作者：CSDN515
