Zju 1082 루머 의 전파 Floyed 알고리즘 - 물 문제

중국 역사상 가장 위대 한 SPY 김 무 태 는 미국의 FBI 에 잠입 해 이 죄악 의 기 구 를 없 애기 위해 FBI 에 가짜 소식 을 퍼 뜨리 기로 했다.그 는 먼저 FBI 의 한 직원 을 선정 해 소문 을 퍼 뜨 린 뒤 이 사람 은 그 가 아 는 모든 사람 에 게 소식 을 알려 줄 것 이다. 물론 이 과정 에서 어느 정도 시간 이 걸 릴 것 이다.그리고 이 사람들 은 또 그 가 아 는 모든 사람 에 게 소식 을 알 릴 것 이다.이런 소식 은 FBI 전체 에 퍼 질 수 있다. 물론 모든 사람 이 이 소식 을 알 고 있 는 시간 이 먼저 있다.우 리 는 이 소식 을 가장 늦게 알 게 된 사람 이 그 가 필요 로 하 는 시간 이 짧 을 수록 좋 기 를 바란다.그렇다면 김 무 태 는 어떤 사람 을 소식 의 선발 로 뽑 아야 할 까?이 사람의 번호 와 T 를 출력 해 주세요.만약 소식 이 FBI 에 퍼 지지 않 는 다 면 'disjoint' 를 출력 해 주 십시오.Input 은 FBI 에 직원 이 몇 명인 지 를 먼저 알려 주 고 숫자 N (N < = 100) 으로 대표 한다.다음 N 행 은 이 N 명의 직원 을 묘사 하 는 데 쓰 인 다.각 줄 마다 이 직원 에 게 몇 명 을 알 고 있 는 지 알려 주 고 아 는 직원 의 번 호 를 알려 주 고 소식 을 전 하 는 데 걸 리 는 시간 을 줍 니 다. Output 예 를 들 어 Sample Input 3, 2, 4, 3, 5, 2, 3, 2, 1, 2 Sample Output 3, 2 는 전형 적 인 플 로 이 드 문제 입 니 다. i 인 을 읽 을 때 플 로 이 드 를 한 번 읽 고 i 와 마지막 으로 소식 을 받 은 사람의 최 단 길 을 계산 하 는 것 입 니 다.그리고 나 와 서 ans 는 INTMAX, if (sans), s 를 적 는 김 에 번 호 를 적 으 세 요. 코드 는 다음 과 같 습 니 다.

#include
#include
#include
using namespace std;
int n,k,m,t,w[101][101],mark,minl,ans;
const int maxx=0x7fffffff;
const int N=100000000;
int main()
{
	memset(w,63,sizeof(w));
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&k);
		for(int j=1;j<=k;j++)
		{
			scanf("%d%d",&m,&t);
			w[i][m]=t;// i           。
		}
	    for(int k=1;k<=n;k++)
	        for(int i=1;i<=n;i++)
	            for(int j=1;j<=n;j++)
	            {
	        	    if(i!=j&&j!=k&&w[i][j]>w[i][k]+w[k][j])//Floyed
	        	    {
	        		    w[i][j]=w[i][k]+w[k][j];
				    }
		        }
     }
        ans=maxx;
		for(int i=1;i<=n;i++)
		{
			int s=0;
			for(int j=1;j<=n;j++)
			{
				if(i!=j)
				   s=max(s,w[i][j]);//      ，  s=0      ，             cost
			}
			if(ss)
			{
				ans=s;//    ans mark
				mark=i;
			}
		}
    if(ans>N)
    {
    	printf("disjoint
");
	}
	else
	{
		printf("%d %d",mark,ans);
	}
	return 0;
}

자, 제 블 로그 가 좋다 고 생각 하 시 면 본 건 33951 건 입 니 다. 시청 해 주 셔 서 감사합니다.