游客 注册 | 登录
中文 | En

1925 - 小道消息

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

公司老总想把一条小道消息以最快的时间传递给公司的的所有的人。但是每个人自己只把消息传给他认识的人，并且传递给他认识的人也需要一定的时间。请你帮助公司老总策划下首先应该把消息告诉谁，然后消息从这个人开始传播直到所有的人都知道此消息，所需的时间最短。（老总把消息告诉第一人知道消息的人不花时间）

题目输入

第一行一个整数n（1 <= n <= 100）表示公司的人数（老总除外）
接下来n行的第i行。每行开头是一个整数m，表示第i人所认识的人数。之后m对整数xj，tj，表示第i人所认识的人的编号为xj，且把消息传递给他需要tj个时间。(1 <= tj <= 10)

题目输出

输出二个整数：首先应该告诉的人的编号a和告诉他之后所需的时间t，两数字用一个空格隔开。但是如果消息无法全部传到所有人那，输出：“disjointdd”。

输入/输出样例

输入格式

3
2 2 4 3 5
2 1 2 3 6
2 1 2 2 2

输出格式

3 2

C++解答

#include<stdio.h>
#include<string.h>
#define INF 0xffffff
#define Max 100

void Floyd(int map[][Max], int n)
{
	int A[Max][Max];
	int i, j, k;
	for(i = 0; i < n; i++){
		for(j = 0; j < n; j++){
			A[i][j] = map[i][j];
		}
	}
	for(k = 0; k < n; k++){
		for(i = 0; i < n; i++)
			for(j = 0; j < n; j++)
				if(A[i][j] > A[i][k]+A[k][j])
					A[i][j] = A[i][k]+A[k][j];
	}
	int min, min_max, yes = 0, x;
	for(i = 0; i < n; i++){
		min_max = 0;
		for(j = 0; j < n; j++){
			if(A[i][j] > min_max)
				min_max = A[i][j];
		}
		if(min_max < INF)yes = 1;
		else if(i) continue;
		if(!i) { x = i; min = min_max; }
		else if(min_max < min){
			x = i; min = min_max;
		}
	}
	if(yes) printf("%d %d\n", x+1, min);
	else printf("disjoint\n");
}

int main()
{
	int n, map[Max][Max], m, x, v;
	int i, j;
	scanf("%d", &n);
		for(i = 0; i < n; i++){
			for(j = 0; j < n; j++)
				if(i != j)map[i][j] = INF;
				else map[i][j] = 0;
		}
		for(i = 0; i < n; i++){
			scanf("%d", &m);
			for(j = 0; j < m; j++){
				scanf("%d%d", &x, &v);
				map[i][x-1] = v;
			}
		}
	Floyd(map, n);
	return 0;
}
请先登陆