Stockbroker Grapevine
| Time Limit:
1000MS |
| Memory Limit: 10000K |
| Total
Submissions: 12398 |
| Accepted:
6649 |
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
题意描述：
1.求每个点到其他各点的最短路径D[i][j]
2.求出D的每行中的最大值中的最小值
注意对Dist[i][j](i == j)的处理
#include <cstdio>
using namespace std;
#define SIZE 110
#define MAX 1000000
int sb, n, Dist[SIZE][SIZE], max[SIZE];
void init()
{
int i, j;
for (i=0 ; i<SIZE ; i++)
for (j=0 ; j<SIZE ; j++)
Dist[i][j] = MAX;
}
void floyd(int size)
{
int i, j, k;
for (k=1 ; k<=size ; k++)
for (i=1 ; i<=size ; i++)
for (j=1 ; j<=size ; j++)
{
/* skip Dist[i][j] */
if (i == j)
continue;
if (Dist[i][j] > Dist[i][k] + Dist[k][j])
Dist[i][j] = Dist[i][k] + Dist[k][j];
}
}
void find_min(int size)
{
int i, j, person, max_time;
bool disjoint;
for (i=1 ; i<=size ; i++)
{
disjoint = false;
max_time = 0;
for (j=1 ; j<=size ; j++)
{
/* skip Dist[i][j] */
if (i == j)
continue;
/*有点不可达，标记为disjoint*/
if (Dist[i][j] >= MAX)
{
disjoint = true;
break;
}
if (Dist[i][j] > max_time)
max_time = Dist[i][j];
}
if (true == disjoint)
max[i] = MAX;
else
max[i] = max_time;
}
/*
printf("max:");
for (i=1 ; i<=size ; i++)
printf("%d ", max[i]);
printf("\n");
*/
int min = MAX, min_idx;
for (i=1 ; i<=size ; i++)
{
if (max[i] < min)
{
min = max[i];
min_idx = i;
}
}
if (MAX == min)
printf("disjoint\n");
else
printf("%d %d\n", min_idx, min);
}
int main(int argc, char *argv[])
{
int i, j, b, t;
while (1)
{
scanf("%d", &sb);
if (0 == sb)
break;
init();
for (i=1 ; i<=sb ; i++)
{
scanf("%d", &n);
for (j=0 ; j<n ; j++)
{
scanf("%d %d", &b, &t);
Dist[i][b] = t;
}
}
floyd(sb);
/*
for (i=1 ; i<=sb ; i++)
{
for (j=1 ; j<=sb ; j++)
printf("%d ", Dist[i][j]);
printf("\n");
}
*/
find_min(sb);
}
}
|
在图论中经常会遇到这样的问题，在一个有向图里，求出任意两个节点之间的最短距离。当节点之间的权值是正值的时候，我们可以采用Dijkstra算
法，用贪心策略加于解决。但当节点之间的权值有负数的时候，Dijkstra就行不通了，这里介绍另外一种算法——Floyd最短路径算法。
问题
描述：
如果有一个矩阵D=[d(ij)]，其中d(ij)>0表示i城市到j城市的距离。若i与j之间无路可通，那么
d(ij)就是无穷大。又有d(ii)=0。编写一个程序，通过这个距离矩阵D，把任意两个城市之间的最短路径找出来。
【分析】
如何找出最短路径呢，这里需要用到动态规划的思想，对于任何一个城市而言，i 到 j 的最短距离不外乎存在经过 i
与 j
之间的k和不经过k两种可能，所以可以令k=1，2，3，...，n(n是城市的数目)，再检查d(ij)与d(ik)+d(kj)的值；在此d(ik)
与d(kj)分别是目前为止所知道的 i 到 k 与 k 到 j 的最短距离，因此d(ik)+d(kj)就是 i 到 j
经过k的最短距离。所以，若有d(ij)>d(ik)+d(kj)，就表示从 i 出发经过 k 再到j的距离要比原来的 i 到 j
距离短，自然把i到j的d(ij)重写为d(ik)+d(kj)<这里就是动态规划中的决策>，每当一个k查完了，d(ij)就是目前的 i
到 j 的最短距离。重复这一过程，最后当查完所有的k时，d(ij)里面存放的就是 i 到 j
之间的最短距离了<这就是动态规划中的记忆化搜索>。利用一个三重循环产生一个存储每个结点最短距离的矩阵.
用
三个for循环把问题解决了，但是有一个问题需要注意，那就是for循环的嵌套的顺序：我们可能随手就会写出这样的枚举程序，但是仔细考虑的话，会发现是
有问题的：
for i:=1 to n do
for j:=1 to n do
for
k:=1 to n do
if.....
问题出在我们太早的把i-k-j的距离确定
下来了，假设一旦找到了i-p-j最短的距离后，i到j就相当处理完了，以后不会在改变了，一旦以后有使i到j的更短的距离时也不能再去更新了，所以结果
一定是不对的。所以应当象下面一样来写程序：
for k:=1 to n do
for i:=1 to n do
for
j:=1 to n do
if .....
这样作的意义在于固定了k，把所有i到j
而经过k的距离找出来，然后象开头所提到的那样进行比较和重写，因为k是在最外层的，所以会把所有的i到j都处理完后，才会移动到下一个K。
阅读(1324) | 评论(0) | 转发(0) |
